#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
vector<int>vpl[500005];
int ar[500005];
int n;
struct SGTR{
int l;int r;
int lz;
int mx;int mn;
}tr[2000006];
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));
}
int ok(int K){
buildtr(1,1,n);
for(int i=1;i<=n;i++){
upd(1,i,-1);
}
for(int i=1;i<=n;i++){
for(int j=0;j<vpl[i].size();j++){
upd(1,vpl[i][j],2);
}
for(int j=K-1;j<vpl[i].size();j++){
int lpl=vpl[i][j-K+1];int rpl=vpl[i][j];
if( ((rpl-lpl+1)-K)<=K ){return 1;}
int rv=qmx(1,rpl,rpl);int lv=(lpl==1)?0:qmx(1,lpl-1,lpl-1);
if(rv==0||rv==1){return 1;}
if(rv<0){
int lmn=(lpl==1)?0:qmn(1,1,lpl-1);
int rmx=qmx(1,rpl,n);
if(rmx-lmn>=0){
return 1;
}
}
}
}
buildtr(1,1,n);
for(int i=1;i<=n;i++){
upd(1,i,-1);
}
for(int i=n;i>=1;i--){
for(int j=0;j<vpl[i].size();j++){
upd(1,vpl[i][j],2);
}
for(int j=K-1;j<vpl[i].size();j++){
int lpl=vpl[i][j-K+1];int rpl=vpl[i][j];
if( ((rpl-lpl+1)-K)<=K ){return 1;}
int rv=qmx(1,rpl,rpl);int lv=(lpl==1)?0:qmx(1,lpl-1,lpl-1);
if(rv==0||rv==1){return 1;}
if(rv<0){
int lmn=(lpl==1)?0:qmn(1,1,lpl-1);
int rmx=qmx(1,rpl,n);
if(rmx-lmn>=0){
return 1;
}
}
}
}
return 0;
}
int fslv(){
//cin>>n;
for(int i=1;i<=n;i++){
// cin>>ar[i];
vpl[ar[i]].push_back(i);
}
int ans=1;
for(int i=n;i>=1;i--){
ans=max(ans,ok(i)*i);
if(ans>1){return i;}
}
return ans;
int l=1;int r=n;
while(l<r){
int mi=l+(r-l+1)/2;
if(ok(mi)){
l=mi;
}else{
r=mi-1;
}
}
// cout<<l<<endl;
return l;
}
int sequence(int N, std::vector<int> A) {
n=N;
for(int i=0;i<n;i++){
ar[i+1]=A[i];
}
return fslv();
return 0;
}
/*
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>ar[i];
vpl[ar[i]].push_back(i);
}
int l=1;int r=n;
while(l<r){
int mi=l+(r-l+1)/2;
if(ok(mi)){
l=mi;
}else{
r=mi-1;
}
}
cout<<l<<endl;
return 0;
}
*/
