#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=5e5+50,inf=1e9;
int n;vector<int>a;
struct Node{int mn,maks;};
Node Merge(Node a,Node b){return {min(a.mn,b.mn),max(a.maks,b.maks)};}
struct SegTree{
int root,nc,lc[2*N],rc[2*N],lazy[2*N];Node node[2*N];
void update(int &c,int x){if(!c)c=++nc;node[c].mn+=x;node[c].maks+=x;lazy[c]+=x;}
void push(int &c){if(!c)c=++nc;update(lc[c],lazy[c]);update(rc[c],lazy[c]);lazy[c]=0;}
void Update(int &c,int ss,int se,int qs,int qe,int x){
if(!c)c=++nc;
if(qs>qe||qe<ss||se<qs)return;
if(qs<=ss&&se<=qe){update(c,x);return;}
int mid=ss+se>>1;push(c);
if(qe<mid+1) Update(lc[c],ss,mid,qs,qe,x);
else if(mid<qs) Update(rc[c],mid+1,se,qs,qe,x);
else Update(lc[c],ss,mid,qs,qe,x),Update(rc[c],mid+1,se,qs,qe,x);
node[c]=Merge(node[lc[c]],node[rc[c]]);
}
void Update(int i,int x){Update(root,0,n,i,n,x);}
Node Get(int &c,int ss,int se,int qs,int qe){
if(!c)c=++nc;
if(qs>qe||qe<ss||se<qs)return {inf,-inf};
if(qs<=ss&&se<=qe) return node[c];
int mid=ss+se>>1;push(c);
if(qe<mid+1) return Get(lc[c],ss,mid,qs,qe);
else if(mid<qs) return Get(rc[c],mid+1,se,qs,qe);
return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
}ST,ST1;
vector<int>ind[N];
bool Check(int x,int i,int j){
Node y=ST.Get(ST.root,0,n,0,ind[x][i]-1),z=ST.Get(ST.root,0,n,ind[x][j],n);
int v1=z.maks-y.mn;
y=ST1.Get(ST1.root,0,n,0,ind[x][i]-1),z=ST1.Get(ST1.root,0,n,ind[x][j],n);
int v2=z.mn-y.maks;
if((v1>=0&&v2<=0)||(v1<=0&&v2>=0)) return true;
return false;
}
int sequence(int n1,vector<int>A){
n=n1;a={0};for(auto i:A) a.pb(i);
for(int i=1;i<=n;i++) ind[i].pb(0);
for(int i=1;i<=n;i++) ind[a[i]].pb(i);
for(int i=1;i<=n;i++) ind[i].pb(n+1);
int res=1;
for(int i=1;i<=n;i++) ST.Update(i,1),ST1.Update(i,1);
for(int x=1;x<=n;x++){
for(int i=1;i+1<ind[x].size();i++) ST1.Update(ind[x][i],-2);
for(int i=1,j=i;i+1<ind[x].size();i++){
while(j+1<ind[x].size()&&Check(x,i,j)) j++;
res=max(res,j-i);
}
for(int i=1;i+1<ind[x].size();i++) ST.Update(ind[x][i],-2);
}
return res;
}
