#include <bits/stdc++.h>
using namespace std;
const int INF=500001;
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
pair<pi,pi> minp(pair<pi,pi> p1,pair<pi,pi> p2){
return mp(mp(min(p1.fi.fi,p2.fi.fi),min(p1.fi.se,p2.fi.se)),mp(min(p1.se.fi,p2.se.fi),min(p1.se.se,p2.se.se)));
}
struct segtree{
int n;
int val;
bool tp;
vector<pair<pi,pi>> seg;
vector<pi> lazy;
void Build(int l,int r,int pos){
if(l==r){
seg[pos]=mp(mp(-l,l),mp(l,-l));
lazy[pos]=mp(0,0);
return;
}
int mid=(l+r)/2;
Build(l,mid,2*pos);
Build(mid+1,r,2*pos+1);
seg[pos]=minp(seg[2*pos],seg[2*pos+1]);
}
void UpdateLazy(int l,int r,int pos){
if(lazy[pos]==mp(0,0)) return;
seg[pos]=mp(mp(seg[pos].fi.fi+lazy[pos].fi,seg[pos].fi.se-lazy[pos].fi),mp(seg[pos].se.fi+lazy[pos].se,seg[pos].se.se-lazy[pos].se));
if(l!=r){
lazy[2*pos]=mp(lazy[2*pos].fi+lazy[pos].fi,lazy[2*pos].se+lazy[pos].se);
lazy[2*pos+1]=mp(lazy[2*pos+1].fi+lazy[pos].fi,lazy[2*pos+1].se+lazy[pos].se);
}
lazy[pos]=mp(0,0);
}
void Update(int l,int r,int pos,int ql,int qr,int tp){
UpdateLazy(l,r,pos);
if(ql<=l && qr>=r){
if(tp==0)lazy[pos]=mp(lazy[pos].fi+2,lazy[pos].se);
else lazy[pos]=mp(lazy[pos].fi,lazy[pos].se-2);
UpdateLazy(l,r,pos);
return;
}
if(ql>r || qr<l) return;
int mid=(l+r)/2;
Update(l,mid,2*pos,ql,qr,tp);
Update(mid+1,r,2*pos+1,ql,qr,tp);
seg[pos]=minp(seg[2*pos],seg[2*pos+1]);
}
pair<pi,pi> Query(int l,int r,int pos,int ql,int qr){
UpdateLazy(l,r,pos);
if(ql<=l && qr>=r){
return seg[pos];
}
if(ql>r || qr<l){
return mp(mp(INF,INF),mp(INF,INF));
}
int mid=(l+r)/2;
return minp(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
}
segtree(int n){
this->n=n;
for(int i=0;i<4*n+4;i++){
seg.push_back(mp(mp(0,0),mp(0,0)));
lazy.push_back(mp(0,0));
}
Build(0,n,1);
}
};
int sequence(int n,vector<int> A){
int x=-1;
int a[n];
int b[n];
int cnt[n]={};
vector<int> ind[n];
for(int i=0;i<n;i++){
A[i]--;
cnt[A[i]]++;
ind[A[i]].push_back(i);
}
for(int i=0;i<n;i++){
a[i]=-1;
b[i]=1;
}
auto st=segtree(n);
int ans=0;
sort(A.begin(),A.end());
ans=max(ans,cnt[A[(n)/2]]);
ans=max(ans,cnt[A[(n+1)/2]]);
while(x<n-1){
x++;
for(int i:ind[x]){
a[i]=1;
st.Update(0,n,1,i+1,n,0);
}
if(x!=0) for(int i:ind[x-1]){
b[i]=-1;
st.Update(0,n,1,i+1,n,1);
}
int l=0;
int r=n;
int m=(l+r+1)/2;
vector<pair<pi,pi>> t1;
vector<pair<pi,pi>> t2;
for(int i=0;i<cnt[x];i++){
t1.push_back(st.Query(0,n,1,0,ind[x][i]));
t2.push_back(st.Query(0,n,1,ind[x][i]+1,n));
}
while(l!=r){
bool pssble=false;
for(int i=0;i<cnt[x]-m+1;i++){
if(-t1[i].fi.se>=t2[i+m-1].fi.fi && -t2[i+m-1].fi.se>=t1[i].fi.fi){
pssble=true;
break;
}
if(-t1[i].se.se>=t2[i+m-1].se.fi && -t2[i+m-1].se.se>=t1[i].se.fi){
pssble=true;
break;
}
}
if(pssble) l=m;
else r=m-1;
m=(l+r+1)/2;
}
ans=max(ans,m);
}
return ans;
}
