#include<bits/stdc++.h>
#include"sequence.h"
using namespace std;
using ll=long long;
#pragma GCC optimize("O3")
const ll N1=5e5+5;
vector<ll>pos[N1];
ll a[N1],n;
struct node{
ll mx,mn,sum;
}st[4*N1];
node mrg(node x,node y){
node ret;
ret.sum=x.sum+y.sum;
ret.mn=min(x.mn,x.sum+y.mn);
ret.mx=max(x.mx,x.sum+y.mx);
return ret;
}
void bd(ll i=1,ll l=1,ll r=n){
if(l==r){
if(a[l]==1)st[i].sum=0;
else st[i].sum=1;
st[i].mx=st[i].sum;
st[i].mn=0;
return;
}
ll md=(l+r)/2;
bd(i*2,l,md);
bd(i*2+1,md+1,r);
st[i]=mrg(st[i*2],st[i*2+1]);
}
void upd(ll id,ll x,ll i=1,ll l=1,ll r=n){
if(l==r){
st[i].sum=x;
st[i].mn=min((ll)0,st[i].sum);
st[i].mx=max((ll)0,st[i].sum);
return;
}
ll md=(l+r)/2;
if(id<=md)upd(id,x,i*2,l,md);
else upd(id,x,i*2+1,md+1,r);
st[i]=mrg(st[i*2],st[i*2+1]);
}
node qry(ll l,ll r,ll i=1,ll tl=1,ll tr=n){
if(tl>=l&&tr<=r)return st[i];
ll md=(tl+tr)/2;
node ret={-(ll)2e9,(ll)2e9,(ll)0};
if(md>=l)ret=mrg(ret,qry(l,r,i*2,tl,md));
if(md+1<=r)ret=mrg(ret,qry(l,r,i*2+1,md+1,tr));
return ret;
}
array<ll,2>getR(ll j,ll x){
ll p2=pos[x][j];
node RG=qry(p2,n);
node M=qry(1,p2-1);
array<ll,2>rgt={M.sum+RG.mn,M.sum+RG.mx};
return rgt;
}
array<ll,2>getL(ll i,ll x){
ll p1=pos[x][i];
node LF=(p1!=1?qry(1,p1-1):(node){0,0,0});
array<ll,2>lef={LF.mn,LF.mx};
return lef;
}
ll L1[N1],R1[N1],L2[N1],R2[N1];
struct{
ll mn,mx;
}ST[4*N1];
void bd2(ll i,ll l,ll r){
if(l==r){
ST[i].mx=R1[l]-l;
ST[i].mn=L1[l]+l;
return;
}
ll md=(l+r)/2;
bd2(i*2,l,md);
bd2(i*2+1,md+1,r);
ST[i].mx=max(ST[i*2].mx,ST[i*2+1].mx);
ST[i].mn=min(ST[i*2].mn,ST[i*2+1].mn);
}
ll Q(ll i,ll X,ll Y,ll tl,ll tr,ll l,ll r){
if(tr<l||tl>r||ST[i].mx<X||ST[i].mn>Y)return 1e18;
if(tl==tr)return tr;
ll md=(tl+tr)/2,rt=Q(i*2,X,Y,tl,md,l,r);
if(rt!=1e18)return rt;
return Q(i*2+1,X,Y,md+1,tr,l,r);
}
ll sol(ll x){
ll sz=pos[x].size();
if(!sz)return 0;
for(int i=0;i<sz;++i){
array<ll,2>TMP=getL(i,x);
L1[i]=TMP[0];
R1[i]=TMP[1];
if(!i)continue;
TMP=getR(i,x);
L2[i]=TMP[0];
R2[i]=TMP[1];
}
for(int i=0;i<=4*sz;++i){
ST[i].mn=1e18;
ST[i].mx=-1e18;
}
bd2(1,0,sz-1);
ll ret=1;
for(int i=1;i<sz;++i)
ret=max(ret,1+i-Q(1,L2[i]-i-1,R2[i]+i+1,0,sz-1,0,i-1));
//sad ocu da uzmem (l<r) t.d.
//1) [l1,r1] i [l2,r2] se seku
//ili l1 element [l2,r2], ili r1 element [l2,r2]
//2) l2-r1 <= r-l+1, l2-r1>=0
//l-r1 <= r-l2+1, r1<=l2, najmanje l t.d.
//3) l1-r2 <= r-l+1, l1-r2>=0
//l+l1 <= r+r2+1, l1>=r2
return ret;
}
int sequence(int _n,vector<int>_a){
n=_n;
for(int i=1;i<=n;++i)
a[i]=_a[i-1];
for(int i=1;i<=n;++i)
pos[i].clear();
for(int i=1;i<=n;++i)
pos[a[i]].push_back(i);
bd(); //za 1
ll ans=sol(1),MM=*max_element(a+1,a+n+1);
//ll ans=sol(4);
for(int i=2;i<=MM;++i){
for(ll x:pos[i-1])upd(x,-1);
for(ll x:pos[i])upd(x,0);
ll D=sol(i);
ans=max(ans,D);
}
return ans;
}
//signed main(){cout<<sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});}
