#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 500007
using namespace std;
int n,a[MAXN],ans,c[MAXN];
vector<int> poss[MAXN];
const int bucket_sz=200;
struct node{
int sum;
int minpref,maxpref;
inline friend node operator + (node fr,node sc){
return {fr.sum+sc.sum,min(fr.minpref,fr.sum+sc.minpref),max(fr.maxpref,fr.sum+sc.maxpref)};
}
}curr;
struct ST{
node tree[4*MAXN];
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v].sum=val;
tree[v].minpref=min(val,0);
tree[v].maxpref=max(val,0);
}else{
int tt=(l+r)/2;
if(pos<=tt)update(2*v,l,tt,pos,val);
else update(2*v+1,tt+1,r,pos,val);
tree[v]=tree[2*v]+tree[2*v+1];
}
}
node getinfo(int v,int l,int r,int ll,int rr){
if(ll>rr)return {0,0,0};
if(l==ll and r==rr){
return tree[v];
}else{
int tt=(l+r)/2;
return getinfo(2*v,l,tt,ll,min(tt,rr)) + getinfo(2*v+1,tt+1,r,max(tt+1,ll),rr);
}
}
}seg;
struct nodd{
int l,r,val;
};
nodd t[150*MAXN];
int num;
struct ST2{
int root;
void init(){
num++;
t[num]={0,0,10*n};
root=num;
}
void addnode(){
num++;
t[num]={0,0,10*n};
}
void check(int v){
if(t[v].l==0){
addnode(); t[v].l=num;
}
if(t[v].r==0){
addnode(); t[v].r=num;
}
}
void update(int v,int l,int r,int pos,int val){
if(l==r){
t[v].val=min(val,t[v].val);
}else{
int tt=(l+r)/2;
check(v);
if(pos<=tt)update(t[v].l,l,tt,pos,val);
else update(t[v].r,tt+1,r,pos,val);
t[v].val=min(t[t[v].l].val,t[t[v].r].val);
}
}
int getmin(int v,int l,int r,int ll,int rr){
if(v==0 or ll>rr)return 10*n;
if(l==ll and r==rr)return t[v].val;
int tt=(l+r)/2;
return min( getmin(t[v].l,l,tt,ll,min(tt,rr)) , getmin(t[v].r,tt+1,r,max(tt+1,ll),rr) );
}
}segx[2*MAXN],segy[2*MAXN];
int solve(int val){
int res=0;
for(int ii=0;ii<poss[val].size();ii++){
for(int ff=ii;ff<poss[val].size();ff++){
int i=poss[val][ii];
int f=poss[val][ff];
int sum=seg.getinfo(1,1,n,i+1,f-1).sum;
curr=seg.getinfo(1,1,n,f,n);
int minpref=curr.minpref,maxpref=curr.maxpref;
curr=seg.getinfo(1,1,n,1,i);
int minsuff=curr.sum-curr.maxpref,maxsuff=curr.sum-curr.minpref;
if((ff-ii+1)>=sum+minpref+minsuff and (ff-ii+1)>=-sum-maxpref-maxsuff)res=max(res,(ff-ii+1));
}
}
return res;
}
struct event{
int val,x,y;
inline friend bool operator < (event fr,event sc){
return fr.val<sc.val;
}
};
set<event> xx,yy;
int A,B,C;
void incrx(){
xx.insert({segx[B-(A-C)+n].getmin(segx[B-(A-C)+n].root,0,2*n,0,B+(A-C)+n),B-(A-C)+n,B+(A-C)+n});
}
void incry(){
yy.insert({segy[B+(A-C)+n].getmin(segy[B+(A-C)+n].root,0,2*n,0,B-(A-C)+n),B-(A-C)+n,B+(A-C)+n});
}
int mins(){
while(!xx.empty()){
auto it=xx.begin();
event curr=*it;
if(curr.x>B-(A-C)+n){
xx.erase(it); continue;
}
if(curr.y>B+(A-C)+n){
xx.erase(it); continue;
}
break;
}
while(!yy.empty()){
auto it=yy.begin();
event curr=*it;
if(curr.x>B-(A-C)+n){
yy.erase(it); continue;
}
if(curr.y>B+(A-C)+n){
yy.erase(it); continue;
}
break;
}
int res=10*n;
if(!xx.empty()){
auto it=xx.begin();
event s=*it; res=min(res,s.val);
}
if(!yy.empty()){
auto it=yy.begin();
event s=*it; res=min(res,s.val);
}
return res;
}
int bigsolve(int val){
int res=0;
A=B=C=0;
xx.clear(); yy.clear();
num=0;
for(int i=0;i<=2*n;i++){
segx[i].init(); segy[i].init();
}
segx[n].update(segx[n].root,0,2*n,n,0);
segy[n].update(segy[n].root,0,2*n,n,0);
xx.insert({0,n,n});
yy.insert({0,n,n});
for(int i=1;i<=n;i++){
if(a[i]>val)A++;
if(a[i]<val)C++;
if(a[i]==val)B++;
segx[B-(A-C)+n].update(segx[B-(A-C)+n].root,0,2*n,B+(A-C)+n,B);
segy[B+(A-C)+n].update(segy[B+(A-C)+n].root,0,2*n,B-(A-C)+n,B);
if(a[i]>val){
incry();
}
if(a[i]<val){
incrx();
}
if(a[i]==val){
incrx(); incry();
}
res=max(res,B-mins());
}
return res;
}
int sequence(int N, std::vector<int> A){
n=N;
for(int i=1;i<=n;i++){
a[i]=A[i-1];
poss[a[i]].push_back(i);
seg.update(1,1,n,i,1);
}
for(int i=1;i<=n;i++){
for(int f:poss[i-1])seg.update(1,1,n,f,-1);
for(int f:poss[i])seg.update(1,1,n,f,0);
if(poss[i].size()<=0)ans=max(ans,solve(i));
else ans=max(ans,bigsolve(i));
}
return ans;
}
/*int main(){
//cout<<sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1})<<"\n";
//cout<<sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2})<<"\n";
return 0;
}*/
