#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
vector<int>vpl[500005];
vector<int>vplv[500005];
int ar[500005];
int n;
struct SEGMENT_TREE{
struct SGTR{
int l;int r;
int lz;
int mx;int mn;
};
vector<SGTR>tr;
void init(int n){
for(int i=0;i<=n*4+10;i++){
tr.push_back({0,0,0,0,0});
}
}
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].lz=0;tr[nw].mx=0;tr[nw].mn=0;
if(l==r){return;}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void psh(int nw){
int ad=tr[nw].lz;
tr[nw].lz=0;
tr[nw*2].lz+=ad;tr[nw*2+1].lz+=ad;
tr[nw*2].mx+=ad;tr[nw*2+1].mx+=ad;
tr[nw*2].mn+=ad;tr[nw*2+1].mn+=ad;
}
void upd(int nw,int l,int v){
if(tr[nw].l>=l){
tr[nw].mx+=v;
tr[nw].mn+=v;
tr[nw].lz+=v;
return;
}
if(tr[nw].r<l){return;}
if(tr[nw].lz){psh(nw);}
upd(nw*2,l,v);
upd(nw*2+1,l,v);
tr[nw].mx=max(tr[nw*2].mx,tr[nw*2+1].mx);
tr[nw].mn=min(tr[nw*2].mn,tr[nw*2+1].mn);
}
int qmx(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
return tr[nw].mx;
}
if(tr[nw].l>r||tr[nw].r<l){return -1e9;}
if(tr[nw].lz){psh(nw);}
return max(qmx(nw*2,l,r),qmx(nw*2+1,l,r));
}
int qmn(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
return tr[nw].mn;
}
if(tr[nw].l>r||tr[nw].r<l){return 1e9;}
if(tr[nw].lz){psh(nw);}
return min(qmn(nw*2,l,r),qmn(nw*2+1,l,r));
}
};
SEGMENT_TREE A;
SEGMENT_TREE B;
int ok(int l,int r){
int rv=A.qmx(1,r,n);
int lv=(l==1)?0:A.qmn(1,1,l-1);
lv=min(lv,0);
if(rv-lv<0){return 0;}
rv=B.qmx(1,r,n);
lv=(l==1)?0:B.qmn(1,1,l-1);
lv=min(lv,0);
if(rv-lv<0){return 0;}
return 1;
}
int fslv(){
//cin>>n;
for(int i=1;i<=n;i++){
// cin>>ar[i];
vpl[ar[i]].push_back(i);
}
int ans=1;
A.init(n);
B.init(n);
A.buildtr(1,1,n);
B.buildtr(1,1,n);
for(int i=1;i<=n;i++){
A.upd(1,i,-1);
B.upd(1,i,1);
}
for(int nw=1;nw<=n;nw++){
for(int i=0;i<vpl[nw].size();i++){
A.upd(1,vpl[nw][i],2);
}
int lit=0;
for(int i=0;i<vpl[nw].size();i++){
while(!ok(vpl[nw][lit],vpl[nw][i])){lit++;}
ans=max(ans,i-lit+1);
}
for(int i=0;i<vpl[nw].size();i++){
B.upd(1,vpl[nw][i],-2);
}
}
// cout<<ans;
return ans;
}
int sequence(int N, std::vector<int> A) {
n=N;
for(int i=0;i<n;i++){
ar[i+1]=A[i];
vpl[i+1].clear();
vplv[i+1].clear();
}
return fslv();
return 0;
}
/*
signed main()
{
return 0;
}
*/
