//#include "festival.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define sz(x) (ll)x.size()
#define cd complex<double>
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=5e5+5;
const ll inf=1e16;
vector<int>g[mxn];
int a[mxn];
struct lazy{
int t[4*mxn]{0},lz[4*mxn]{0};
void push(int i,int l,int r){
t[i]+=lz[i];
if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
lz[i]=0;
}
void update(int i,int l,int r,int tl,int tr,int v){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]+=v;push(i,l,r);return;
}int m=(l+r)>>1;
update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
t[i]=max(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
push(i,l,r);
if(r<tl||l>tr)return -1e9;
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return max(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
}sg[2];
struct lazy2{
vector<int>v,t,lz;
void build(){
sort(all(v));v.erase(unique(all(v)),v.end());
t.resize(4*v.size());
lz.resize(4*v.size());
for(int i=0;i<t.size();i++)t[i]=1e9,lz[i]=1e9;
}
void push(int i,int l,int r){
t[i]=min(t[i],lz[i]);
if(l<r){lz[2*i]=min(lz[i],lz[2*i]);lz[2*i+1]=min(lz[i],lz[2*i+1]);}
lz[i]=1e9;
}
void update(int i,int l,int r,int tl,int tr,int v){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]=v;
push(i,l,r);
return;
}int m=(l+r)>>1;
update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
push(i,l,r);
if(r<tl||l>tr)return 1e9;
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
}st[mxn];
struct seg{
vector<int>v,mx,mn;
void build(){
sort(all(v));v.erase(unique(all(v)),v.end());
mx.resize(2*v.size());
mn.resize(2*v.size());
for(int i=0;i<mx.size();i++)mx[i]=-1e9,mn[i]=1e9;
}
void update(int i,int sz,int amt){
i+=sz;mx[i]=max(mx[i],amt),mn[i]=min(mn[i],amt);
for(i>>=1;i;i>>=1)mx[i]=max(mx[2*i],mx[2*i+1]),mn[i]=min(mn[2*i],mn[2*i+1]);
}
int get_max(int l,int r,int sz,int rs=-1e9){
for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
if(l&1)rs=max(rs,mx[l++]);
if(r&1)rs=max(rs,mx[--r]);
}return rs;
}
int get_min(int l,int r,int sz,int rs=1e9){
for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
if(l&1)rs=min(rs,mn[l++]);
if(r&1)rs=min(rs,mn[--r]);
}return rs;
}
}tl[mxn];
int sequence(int N, std::vector<int> A){
int n=N;
for(int i=1;i<=n;i++)g[A[i-1]].pb(i),sg[0].update(1,0,n,i,n,1),sg[1].update(1,0,n,i,n,-1);
int rs=1;
for(int x=1;x<=n;x++){
if(g[x].empty())continue;
for(auto it : g[x])sg[0].update(1,0,n,it,n,-1),sg[1].update(1,0,n,it,n,1);
vector<t3>v,qv;
int pv=0,cnt=0;
for(auto it : g[x]){
int mx=sg[0].qr(1,0,n,pv,it-1);
int mn=-sg[1].qr(1,0,n,pv,it-1);
st[x].v.pb(mn);st[x].v.pb(mx);
qv.pb({mx,mn,cnt});v.pb({mx+cnt,cnt-mx,cnt});
v.pb({mn+cnt,cnt-mn,cnt});
tl[x].v.pb(cnt-mx);tl[x].v.pb(cnt-mn);
pv=it;cnt++;
}
int mx=sg[0].qr(1,0,n,pv,n);
int mn=-sg[1].qr(1,0,n,pv,n);
st[x].v.pb(mx);st[x].v.pb(mn);
qv.pb({mx,mn,cnt});
v.pb({mx+cnt,cnt-mx,cnt});
v.pb({mn+cnt,cnt-mn,cnt});
tl[x].v.pb(cnt-mx);tl[x].v.pb(cnt-mn);
st[x].build();
for(auto [mx,mn,cur] : qv){
int id = st[x].qr(1,1,st[x].v.size(),ub(st[x].v,mn),ub(st[x].v,mx));
if(id!=1e9)rs=max(rs,abs(cur-id));
st[x].update(1,1,st[x].v.size(),ub(st[x].v,mn),ub(st[x].v,mx),cur);
}
sort(all(v));
tl[x].build();
for(auto [_,it,y] : v){
int mn=tl[x].get_min(0,ub(tl[x].v,it),tl[x].v.size());
int mx=tl[x].get_max(0,ub(tl[x].v,it),tl[x].v.size());
if(mx!=-1e9)rs=max(rs,abs(y-mx));
if(mn!=1e9)rs=max(rs,abs(y-mn));
tl[x].update(lb(tl[x].v,it),tl[x].v.size(),y);
}
for(auto it : g[x])sg[0].update(1,0,n,it,n,-1),sg[1].update(1,0,n,it,n,1);
}return rs;
}
/*int main(){
cout<<sequence(7, {1, 2, 3, 1, 2, 1, 3});
}*/
