#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
struct T{
int Minpre=0,Maxpre=0,Minsuf=0,Maxsuf=0,sum=0;
};
struct segtree{
T Tid;
T TT(T &le,T &ri){
T pa;
pa.sum=le.sum+ri.sum;
pa.Minpre=min(le.Minpre,le.sum+ri.Minpre);
pa.Maxpre=max(le.Maxpre,le.sum+ri.Maxpre);
pa.Minsuf=min(ri.Minsuf,le.Minsuf+ri.sum);
pa.Maxsuf=max(ri.Maxsuf,le.Maxsuf+ri.sum);
return pa;
}
vector<T> seg;
int n,lg;
void refresh(int v){
seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
}
void build(int siz){
n=1;
while(n<siz){
n<<=1;
}
lg=__lg(n);
seg.assign(n<<1,Tid);
}
void update(int l,int x){
l+=n;
seg[l].sum=x;
seg[l].Minpre=min(0,x),seg[l].Maxpre=max(0,x);
seg[l].Minsuf=seg[l].Minpre,seg[l].Maxsuf=seg[l].Maxpre;
for(int i=1;i<=lg;i++){
refresh(l>>i);
}
}
T query(int l,int r){
l+=n,r+=n;
T le=Tid,ri=Tid;
for(;l<r;l>>=1,r>>=1){
if(l&1){
le=TT(le,seg[l]);
l++;
}
if(r&1){
r--;
ri=TT(seg[r],ri);
}
}
return TT(le,ri);
}
};
struct fenwick{
vector<int> bit;
int TT(int le,int ri){
return min(le,ri);
}
int Tid=1e9;
void build(int siz){
bit.resize(siz+1);
for(int i=1;i<=siz;i++){
bit[i]=Tid;
}
}
void update(int i,int x){
for(;i<bit.size();i+=(i&(-i))){
bit[i]=TT(bit[i],x);
}
}
int query(int i){
int curr=Tid;
for(;i;i-=(i&(-i))){
curr=TT(curr,bit[i]);
}
return curr;
}
};
struct point{
int x,y,idx,ope;
};
bool cmp(point &a,point &b){
if(a.x!=b.x){
return (a.x<b.x);
}
return (a.ope<b.ope);
}
int sequence(int n,vector<int> a){
segtree seg;
vector<vector<int>> occu(n+1);
for(int i=0;i<n;i++){
occu[a[i]].push_back(i);
}
seg.build(n);
for(int i=0;i<n;i++){
seg.update(i,1);
}
int ans=1;
for(int x=1;x<=n;x++){
int sz=occu[x].size();
for(int i=0;i<sz;i++){
seg.update(occu[x][i],0);
}
if(sz==0){
continue;
}
vector<point> v;
int sum=0;
map<int,int> mp;
for(int i=0;i<sz;i++){
int pos=occu[x][i],last=-1,nxt=n;
if(i>0){
last=occu[x][i-1];
}
if(i+1<sz){
nxt=occu[x][i+1];
}
T suf=seg.query(last+1,pos+1);
T pre=seg.query(pos,nxt);
sum+=suf.sum;
mp[i-1+sum-suf.Maxsuf]=1;
mp[sum+pre.Maxpre+i]=1;
v.push_back({suf.Minsuf+i-1-sum,i-1+sum-suf.Maxsuf,i,0});
v.push_back({i-sum-pre.Minpre,sum+pre.Maxpre+i,i,1});
}
int idx=1;
for(pair<const int,int> &x:mp){
x.second=idx,idx++;
}
sort(v.begin(),v.end(),cmp);
fenwick bit;
bit.build(idx-1);
for(point &x:v){
x.y=mp[x.y];
if(x.ope==0){
bit.update(x.y,x.idx);
}
else{
ans=max(ans,x.idx-bit.query(x.y)+1);
}
}
for(int i=0;i<sz;i++){
seg.update(occu[x][i],-1);
}
}
return ans;
}
/*signed main(){
cout << sequence(7,{1,2,3,1,2,1,3});
}*/
