//#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[8*mxn]{0},lz[8*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{
int t[8*mxn]{0},lz[4*mxn]{0},lz2[8*mxn]{0};
void push2(int i,int l,int r){
if(lz2[i]==0)return;
t[i]=lz2[i],lz[i]=lz2[i];
if(l<r)lz2[2*i]=lz2[i],lz2[2*i+1]=lz2[i];
lz2[i]=0;
}
void push(int i,int l,int r){
push2(i,l,r);
t[i]=min(t[i],lz[i]);
if(l<r){
int m=(l+r)>>1;
push2(2*i,l,m);
push2(2*i+1,m+1,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]);
}
void reset(int i,int l,int r){
lz2[i]=1e9;push(i,l,r);
}
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));
}
}st2;
struct seg{
int t[16*mxn]{0};
void build(){
for(int i=0;i<8*mxn;i++)t[i]=1e9;
}
void update(int i,int l,int r,int idx,int v){
if(r<idx||l>idx)return;
if(l==r){
t[i]=min(t[i],v);
return;
}int m=(l+r)>>1;
update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
t[i]=min(t[2*i],t[2*i+1]);
}
void reset(int i,int l,int r,int idx,int v){
if(r<idx||l>idx)return;
if(l==r){
t[i]=v;
return;
}int m=(l+r)>>1;
reset(2*i,l,m,idx,v);reset(2*i+1,m+1,r,idx,v);
t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
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));
}
}tr[2];
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);
st2.reset(1,0,2*n);int rs=1;tr[0].build();tr[1].build();
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;
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);
int id=st2.qr(1,0,2*n,mn+n,mx+n);
v.pb({mx+cnt,cnt-mx,cnt});
v.pb({mn+cnt,cnt-mn,cnt});
if(id!=1e9)rs=max(rs,cnt-id);
st2.update(1,0,2*n,mn+n,mx+n,cnt++);pv=it;
}
int mx=sg[0].qr(1,0,n,pv,n);
int mn=-sg[1].qr(1,0,n,pv,n);
v.pb({mx+cnt,cnt-mx,cnt});
v.pb({mn+cnt,cnt-mx,cnt});
int id=st2.qr(1,0,2*n,mn+n,mx+n);
if(id!=1e9)rs=max(rs,cnt-id);
sort(all(v));
for(auto [_,x,y] : v){
int mn=tr[0].qr(1,0,4*n,0,x+2*n);
int mx=-tr[1].qr(1,0,4*n,0,x+2*n);
if(mx!=-1e9)rs=max(rs,abs(y-mx));
if(mn!=1e9)rs=max(rs,abs(y-mn));
tr[0].update(1,0,4*n,x+2*n,y);
tr[1].update(1,0,4*n,x+2*n,-y);
}
for(auto [_,x,y] : v){
tr[0].reset(1,0,4*n,x+2*n,1e9);
tr[1].reset(1,0,4*n,x+2*n,1e9);
}
st2.reset(1,0,2*n);
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});
}*/
