#include <bits/stdc++.h>
using namespace std;
const int INF=500001;
struct segtree{
int n;
int val;
bool tp;
vector<int> seg;
vector<int> lazy;
void Build(int l,int r,int pos){
if(l==r){
seg[pos]=l*val;
lazy[pos]=0;
return;
}
int mid=(l+r)/2;
Build(l,mid,2*pos);
Build(mid+1,r,2*pos+1);
if(tp) seg[pos]=min(seg[2*pos],seg[2*pos+1]);
else seg[pos]=max(seg[2*pos],seg[2*pos+1]);
}
void UpdateLazy(int l,int r,int pos){
if(lazy[pos]==0) return;
seg[pos]+=lazy[pos];
if(l!=r){
lazy[2*pos]+=lazy[pos];
lazy[2*pos+1]+=lazy[pos];
}
lazy[pos]=0;
}
void Update(int l,int r,int pos,int ql,int qr){
UpdateLazy(l,r,pos);
if(ql<=l && qr>=r){
lazy[pos]-=2*val;
UpdateLazy(l,r,pos);
return;
}
if(ql>r || qr<l) return;
int mid=(l+r)/2;
Update(l,mid,2*pos,ql,qr);
Update(mid+1,r,2*pos+1,ql,qr);
if(tp) seg[pos]=min(seg[2*pos],seg[2*pos+1]);
else seg[pos]=max(seg[2*pos],seg[2*pos+1]);
}
int 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){
if(tp) return INF;
else return -INF;
}
int mid=(l+r)/2;
if(tp) return min(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
else return max(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
}
segtree(int n,int val,bool tp){
this->n=n;
this->val=val;
this->tp=tp;
for(int i=0;i<4*n;i++){
seg.push_back(0);
lazy.push_back(0);
}
Build(0,n,1);
}
};
int sequence(int n,vector<int> A){
int x=-1;
int a[n];
int b[n];
int cnt[n+1]={};
vector<int> ind[n+1];
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 mina=segtree(n,-1,true);
auto minb=segtree(n,1,true);
auto maxa=segtree(n,-1,false);
auto maxb=segtree(n,1,false);
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;
mina.Update(0,n,1,i+1,n);
maxa.Update(0,n,1,i+1,n);
}
if(x!=0) for(int i:ind[x-1]){
b[i]=-1;
minb.Update(0,n,1,i+1,n);
maxb.Update(0,n,1,i+1,n);
}
int l=0;
int r=n;
int m=(l+r+1)/2;
vector<int> mn1a;
vector<int> mx1a;
vector<int> mn2a;
vector<int> mx2a;
vector<int> mn1b;
vector<int> mx1b;
vector<int> mn2b;
vector<int> mx2b;
for(int i=0;i<cnt[x];i++){
mn1a.push_back(mina.Query(0,n,1,0,ind[x][i]));
mx1a.push_back(maxa.Query(0,n,1,0,ind[x][i]));
mn2a.push_back(mina.Query(0,n,1,ind[x][i]+1,n));
mx2a.push_back(maxa.Query(0,n,1,ind[x][i]+1,n));
mn1b.push_back(minb.Query(0,n,1,0,ind[x][i]));
mx1b.push_back(maxb.Query(0,n,1,0,ind[x][i]));
mn2b.push_back(minb.Query(0,n,1,ind[x][i]+1,n));
mx2b.push_back(maxb.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(mx1a[i]>=mn2a[i+m-1] && mx2a[i+m-1]>=mn1a[i]){
pssble=true;
break;
}
if(mx1b[i]>=mn2b[i+m-1] && mx2b[i+m-1]>=mn1b[i]){
pssble=true;
break;
}
}
if(pssble) l=m;
else r=m-1;
m=(l+r+1)/2;
}
ans=max(ans,m);
}
return ans;
}
