#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
struct qj{
int l,r;
friend qj operator+(qj a,qj b){
a.l+=b.l;a.r+=b.r;
return a;
}
};
struct node{
int l,r,sl,is;
qj it,iq,h,q,t;
}p[2000005];
vector<int>wz[500005];
int res,n;
void upset(int x){
p[x].t.l=p[x<<1].t.l+p[x<<1|1].t.l;
p[x].t.r=p[x<<1].t.r+p[x<<1|1].t.r;
p[x].q.l=min(p[x<<1].q.l,p[x<<1|1].q.l+p[x<<1].t.l);
p[x].q.r=max(p[x<<1].q.r,p[x<<1|1].q.r+p[x<<1].t.r);
p[x].h.l=min(p[x<<1|1].h.l,p[x<<1].h.l+p[x<<1|1].t.l);
p[x].h.r=max(p[x<<1|1].h.r,p[x<<1].h.r+p[x<<1|1].t.r);
p[x].sl=p[x<<1].sl+p[x<<1|1].sl;
}
void reset(int x,int l,int r){
p[x].l=l,p[x].r=r;
if(l==r){
p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=1;
return;
}
int mid=l+r>>1;
reset(x<<1,l,mid);
reset(x<<1|1,mid+1,r);
upset(x);
}
void sets(int x,int d,int sum){
if(p[x].l==d&&p[x].r==d){
if(sum){
p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=sum;
p[x].sl=0;
}else{
p[x].h.l=p[x].q.l=p[x].t.l=-1;
p[x].h.r=p[x].q.r=p[x].t.r=1;
p[x].sl=1;
}
return;
}
int mid=p[x].l+p[x].r>>1;
if(d<=mid)sets(x<<1,d,sum);
else sets(x<<1|1,d,sum);
upset(x);
}
void gx(int x,int sum){
for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum);
}
qj gets1(int x,int d){
if(d==0)return (qj){0,0};
if(p[x].l==p[x].r){
p[x].it=p[x].t;
return p[x].t;
}
int mid=p[x].l+p[x].r>>1;
qj res=(qj){0,0};
if(d<=mid){
qj nww=gets1(x<<1,d);
p[x].it=p[x<<1].it;
return nww;
}else{
qj rr=gets1(x<<1|1,d);
res.l=min(rr.l,p[x<<1|1].it.l+p[x<<1].h.l);
res.r=max(rr.r,p[x<<1|1].it.r+p[x<<1].h.r);
p[x].it=p[x<<1].t+p[x<<1|1].it;
}
return res;
}
void init(int x,int d){
if(p[x].l==p[x].r){
p[x].it=p[x].t,p[x].iq=p[x].q,p[x].is=p[x].sl;
return;
}
if(p[x<<1].r<d){
init(x<<1|1,d);
p[x].it=p[x<<1|1].it,p[x].iq=p[x<<1|1].iq,p[x].is=p[x<<1|1].is;
return;
}
init(x<<1,d);
p[x].it=p[x<<1].it+p[x<<1|1].t;
p[x].iq.l=min(p[x<<1].iq.l,p[x<<1|1].q.l+p[x<<1].it.l);
p[x].iq.r=max(p[x<<1].iq.r,p[x<<1|1].q.r+p[x<<1].it.r);
p[x].is=p[x<<1].is+p[x<<1|1].sl;
}
int gets(int x,int d,qj sum,int ans,int xy){
if(p[x].l==p[x].r)return ans+p[x].sl;
int mid=p[x].l+p[x].r>>1;
if(d>mid)return gets(x<<1|1,d,sum,ans,1);
if(xy){
qj rt=p[x<<1].it+p[x<<1|1].q+sum;
if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].it,ans+p[x<<1].is,0);
else return gets(x<<1,d,sum,ans,1);
}else{
qj rt=p[x<<1].t+p[x<<1|1].q+sum;
if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].t,ans+p[x<<1].sl,0);
else return gets(x<<1,d,sum,ans,0);
}
}
int sol(int x){
qj fw=gets1(1,x-1);
fw.l=min(0,fw.l),fw.r=max(fw.r,0);
init(1,x);
return gets(1,x,fw,0,1);
}
int solve(int x){
int ans=0;
for(int i=0;i<wz[x].size();i++){
ans=max(ans,sol(wz[x][i]));
}
return ans;
}
int sequence(int N,vector<int>w){
n=N;
reset(1,1,n);
for(int i=0;i<n;i++){
wz[w[i]].push_back(i+1);
}
for(int i=1;i<=n;i++){
gx(i-1,-1);
gx(i,0);
gx(i+1,1);
res=max(res,solve(i));
}
return res;
}
