#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(s) ((int)s.size())
#define pii pair<int,int>
#define F first
#define S second
const int MAX=5e5+10;
const int inf=1e9;
struct segtree{
int mx[4*MAX],mn[4*MAX],add[4*MAX];
void init(){
memset(mx,0,sizeof(mx));
memset(mn,0,sizeof(mn));
memset(add,0,sizeof(add));
}
void upd(int v,int x){
mx[v]+=x;
mn[v]+=x;
add[v]+=x;
}
void push(int v){
if(add[v]){
upd(2*v,add[v]);
upd(2*v+1,add[v]);
add[v]=0;
}
}
void update(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
upd(v,x);
return;
}
push(v);
int tm=(tl+tr)/2;
update(2*v,tl,tm,l,r,x);
update(2*v+1,tm+1,tr,l,r,x);
mx[v]=max(mx[2*v],mx[2*v+1]);
mn[v]=min(mn[2*v],mn[2*v+1]);
}
pii get(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return {inf,-inf};
if(l<=tl&&tr<=r)return {mn[v],mx[v]};
push(v);
int tm=(tl+tr)/2;
pii a=get(2*v,tl,tm,l,r),b=get(2*v+1,tm+1,tr,l,r);
return {min(a.F,b.F),max(a.S,b.S)};
}
}t[2];
int n;
vector<int> pos[MAX];
bool check(int mid){
t[0].init();
t[1].init();
for(int i=1;i<=n;i++){
t[0].update(1,0,n,i,n,1);
t[1].update(1,0,n,i,n,1);
}
for(int i=1;i<=n;i++){
for(int r=sz(pos[i])-1;r>=1;r--){
int l=r-mid+1;
if(l>=1){
int mxR=t[0].get(1,0,n,pos[i][r],n).S;
int mnR=t[1].get(1,0,n,pos[i][r],n).F-2*mid;
int mxL=t[0].get(1,0,n,pos[i][l-1],pos[i][l]-1).S;
int mnL=t[0].get(1,0,n,pos[i][l-1],pos[i][l]-1).F;
// cout<<i<<" "<<pos[i][l]<<" "<<pos[i][r]<<" "<<mnL<<" "<<mxL<<" "<<mnR<<" "<<mxR<<"\n";
if(max(mnL,mnR)<=min(mxL,mxR))return 1;
}
t[1].update(1,0,n,pos[i][r],n,-2);
}
for(int r=1;r<sz(pos[i]);r++){
t[0].update(1,0,n,pos[i][r],n,-2);
}
}
return 0;
}
int sequence(int N,vector<int> a){
n=N;
for(int i=1;i<=n;i++)pos[i].pb(0);
for(int i=0;i<n;i++){
pos[a[i]].pb(i+1);
}
int l=2,r=n,res=1;
while(l<=r){
int m=(l+r)/2;
if(check(m)){
l=m+1;
res=m;
}
else r=m-1;
}
// check(2);
return res;
}
