#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
struct info{
int sum1,sum2,mnl,mnr,mxl,mxr;
info(int v){
mnl=mnr=min(0,sum1=sum2=v),mxl=mxr=max(0,v);
}
info(){
sum1=sum2=mnl=mnr=mxl=mxr=0;
}
info(int x,int y){
sum1=mnl=mnr=x,sum2=mxl=mxr=y;
}
info(info a,info b){
sum1=a.sum1+b.sum1;
sum2=a.sum2+b.sum2;
mnl=min(a.mnl,b.mnl+a.sum1);
mnr=min(b.mnr,a.mnr+b.sum1);
mxl=max(a.mxl,b.mxl+a.sum2);
mxr=max(b.mxr,a.mxr+b.sum2);
}
}T[1<<20];
void update(int i,int l,int r,int p,int x){
if(l==r)
return void(T[i]=info(x));
if(p>l+r>>1)
update(i*2+1,l+r+2>>1,r,p,x);
else update(i*2,l,l+r>>1,p,x);
T[i]=info(T[i*2],T[i*2+1]);
}
void updspec(int i,int l,int r,int p){
if(l==r)
return void(T[i]=info(-1,1));
if(p>l+r>>1)
updspec(i*2+1,l+r+2>>1,r,p);
else updspec(i*2,l,l+r>>1,p);
T[i]=info(T[i*2],T[i*2+1]);
}
info query(int i,int l,int r,int ll,int rr){
if(ll<=l&&r<=rr)
return T[i];
if(l>rr||ll>r)
return T[0];
return info(query(i*2,l,l+r>>1,ll,rr),
query(i*2+1,l+r+2>>1,r,ll,rr));
}
int n=0;
bool ok(int l,int r,int cnt){
int w=query(1,1,n,l,r).sum2-cnt;
if(w<0)
return w+cnt+query(1,1,n,1,l-1).mxr+query(1,1,n,r+1,n).mxl>=0;
return w-cnt+query(1,1,n,1,l-1).mnr+query(1,1,n,r+1,n).mnl<=0;
}
int sequence(int N, std::vector<int> A) {
vector<int> p[N+1];
n=N;
for(int i=1;i<=N;i++)
update(1,1,n,i,1),
p[A[i-1]].push_back(i);
int ans=1;
for(int i=1;i<=N;i++){
int r=0;
for(auto j:p[i])
updspec(1,1,n,j);
for(int l=0;l<(int)p[i].size()-1;l++)
while(r<p[i].size()&&ok(p[i][l],p[i][r],r-l+1))
ans=max(ans,++r-l);
for(auto j:p[i])
update(1,1,n,j,-1);
}
return ans;
}
