#ifdef LOCAL
#include "grader.cpp"
#endif
// #include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2,sse4,bmi2,popcnt")
#define int long long
#define iint signed
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define SQ(x) ((x)*(x))
#define pii pair<int,int>
#define pipii pair<int,pii>
#define ppi pair<pii,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld double
#define pdd pair<ld,ld>
template<typename S> void chmin(S &x,S y) { x=min(x,y); }
template<typename S> void chmax(S &x,S y) { x=max(x,y); }
#define addmod(x,y) x=((x+(y))%mod)
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& os,pair<T1,T2> p) { return os<<'{'<<p.f<<','<<p.s<<'}'; }
template<typename T1,typename T2>
istream& operator>>(istream& os,pair<T1,T2> &p) { return os>>p.f>>p.s; }
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
template<typename T1,typename T2>
pair<T1,T2> operator+(pair<T1,T2> p1,pair<T1,T2> p2) { return pair<T1,T2>(p1.f+p2.f,p1.s+p2.s); }
const int mod=998244353;
const int maxn=1e5+5;
const int maxv=1e6+5;
const int inf=1ll<<60;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int rd(int l,int r) {
// return uniform_int_distribution<int>(l,r)(rng);
// }
struct _IO {
_IO() { ios::sync_with_stdio(0),cin.tie(0); }
} __IO;
struct SEG {
struct Seg {
int mnp,mxp,sum;//min prefix sum, sum
};
Seg merge(Seg b,Seg c) {
Seg a;
a.sum=b.sum+c.sum;
a.mnp=min(b.mnp,b.sum+c.mnp);
a.mxp=max(b.mxp,b.sum+c.mxp);
return a;
}
void pull(Seg &a,Seg &b, Seg &c) {
a=merge(b,c);
}
int n;
vector<Seg> s;
void build(int w,int l,int r,int v) {
if(l==r) {
s[w].sum=v;
s[w].mnp=min(0ll,s[w].sum);
s[w].mxp=max(0ll,s[w].sum);
return;
}
int m=l+r>>1;
build(w<<1,l,m,v);
build(w<<1|1,m+1,r,v);
pull(s[w],s[w<<1],s[w<<1|1]);
}
void init(int _n,int v=0) {
n=_n;
s=vector<Seg>(n<<2);
build(1,0,n-1,v);
};
void _ud(int w,int l,int r,int u,int v) {
if(l==r) {
s[w].sum+=v;
s[w].mnp=min(0ll,s[w].sum);
s[w].mxp=max(0ll,s[w].sum);
return;
}
int m=l+r>>1;
if(u<=m) _ud(w<<1,l,m,u,v);
else _ud(w<<1|1,m+1,r,u,v);
pull(s[w],s[w<<1],s[w<<1|1]);
}
void ud(int u,int v) {
_ud(1,0,n-1,u,v);
}
Seg _qu(int w,int l,int r,int ql,int qr) {
if(ql<=l&&r<=qr) return s[w];
if(ql>r||qr<l) return {0,0,0};
int m=l+r>>1;
return merge(_qu(w<<1,l,m,ql,qr),_qu(w<<1|1,m+1,r,ql,qr));
}
int mn(int l,int r) {
return _qu(1,0,n-1,0,l).sum+_qu(1,0,n-1,l+1,r).mnp;
}
int sum(int l,int r) {
return _qu(1,0,n-1,l,r).sum;
}
int mx(int l,int r) {
return _qu(1,0,n-1,0,l).sum+_qu(1,0,n-1,l+1,r).mxp;
}
};
struct tdBIT {
#undef int
int n,m;
int iss;
vector<unordered_map<int,int>> b;
// unordered_map<int,unordered_map<int,int>> b;
void init(int _n,int _m) {
n=_n,m=_m;
iss=0;
if(n<m) {
swap(m,n);
iss=1;
}
b=vector<unordered_map<int,int>>(n+1);
}
void ud(int x,int y,int v) {
if(iss) swap(x,y);
// assert(x>0&&x<=n&&y>0&&y<=m);
for(int ux=x;ux<=n;ux+=ux&-ux)
for(int uy=y;uy<=m;uy+=uy&-uy)
chmax(b[ux][uy],v);
}
int qu(int x,int y) {
if(iss) swap(x,y);
// assert(x>0&&x<=n&&y>0&&y<=m);
int an=0;
for(int ux=x;ux>0;ux-=ux&-ux)
for(int uy=y;uy>0;uy-=uy&-uy)
if(b[ux].count(uy))chmax(an,b[ux][uy]);
return an;
}
#define int long long
};
iint sequence(iint N, std::vector<iint> A) {
int n=N;
Vi a(n+1);
REP1(i,n) a[i]=A[i-1]-1;
vector<Vi> id(n,{0});
REP1(i,n) id[a[i]].pb(i);
REP(i,n) id[i].pb(n+1);
REP(i,n) {
if(SZ(id[i])-2>=(n+1)/2) {
return SZ(id[i])-2;
}
}
SEG seg;
seg.init(n+1,-1);
int an=0;
REP(i,n) {
auto &v=id[i];
int sz=SZ(v)-2;
REP1(j,sz) seg.ud(v[j],2);
Vi mn(sz+1),mx(sz+1);
REP(j,sz+1) {
mn[j]=seg.mn(v[j],v[j+1]-1);
mx[j]=seg.mx(v[j],v[j+1]-1);
}
tdBIT bit;
bit.init(sz*2+5,sz*2+5);
Vi t,t1;
REP1(j,sz) t.pb(j*2-mn[j]),t1.pb(mx[j]);
REP(j,sz) t.pb(j*2-mx[j]),t1.pb(mn[j]);
sort(ALL(t1));
sort(ALL(t));
REP(j,sz+1) {
if(j){
int x=lower_bound(ALL(t1),mx[j])-t1.begin()+1;
int y=lower_bound(ALL(t),j*2-mn[j])-t.begin()+1;
int ret=bit.qu(x,y);
if(ret>0)chmax(an,j-(sz+1)+ret);
}
if(j<sz){
int x=lower_bound(ALL(t1),mn[j])-t1.begin()+1;
int y=lower_bound(ALL(t),j*2-mx[j])-t.begin()+1;
bit.ud(x,y,sz+1-j);
}
}
// REP1(r,sz) {
// REP(l,r) {
// if(mx[r]>=mn[l]&&mn[r]-r*2<=mx[l]-l*2) {
// chmax(an,r-l);
// }
// }
// }
}
return an;
}
