#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
struct lazymax{
int n;
vector<int> seg;
vector<int> lazy;
void build(int l, int r, int v){
if(l==r){
seg[v]=l;
}else{
int m=(l+r)/2;
build(l,m,2*v);
build(m+1,r,2*v+1);
seg[v]=max(seg[2*v],seg[2*v+1]);
}
}
void push(int v){
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
seg[2*v]+=lazy[v];
seg[2*v+1]+=lazy[v];
lazy[v]=0;
}
void update(int l, int r, int v, int cl, int cr, int x){
if(cl>cr){
return;
}
if(l>r){
return;
}
if(l==cl and r==cr){
seg[v]+=x;
lazy[v]+=x;
return;
}
int m=(l+r)/2;
push(v);
update(l,m,2*v,cl,min(m,cr),x);
update(m+1,r,2*v+1,max(m+1,cl),cr,x);
seg[v]=max(seg[2*v],seg[2*v+1]);
}
int get(int l, int r, int v, int cl, int cr){
if(cl>cr){
return -1e9;
}
if(l>r){
return -1e9;
}
if(l==cl and r==cr){
return seg[v];
}
int m=(l+r)/2;
push(v);
return max(get(l,m,2*v,cl,min(cr,m)),get(m+1,r,2*v+1,max(cl,m+1),cr));
}
lazymax(int n){
this->n=n;
seg.clear();
seg.resize(4*n+5);
lazy.clear();
lazy.resize(4*n+5);
build(1,n,1);
}
};
struct lazymin{
int n;
vector<int> seg;
vector<int> lazy;
void build(int l, int r, int v){
if(l==r){
seg[v]=l;
}else{
int m=(l+r)/2;
build(l,m,2*v);
build(m+1,r,2*v+1);
seg[v]=min(seg[2*v],seg[2*v+1]);
}
}
void push(int v){
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
seg[2*v]+=lazy[v];
seg[2*v+1]+=lazy[v];
lazy[v]=0;
}
void update(int l, int r, int v, int cl, int cr, int x){
if(cl>cr){
return;
}
if(l>r){
return;
}
if(l==cl and r==cr){
seg[v]+=x;
lazy[v]+=x;
return;
}
int m=(l+r)/2;
push(v);
update(l,m,2*v,cl,min(m,cr),x);
update(m+1,r,2*v+1,max(m+1,cl),cr,x);
seg[v]=min(seg[2*v],seg[2*v+1]);
}
int get(int l, int r, int v, int cl, int cr){
if(cl>cr){
return 1e9;
}
if(l>r){
return 1e9;
}
if(l==cl and r==cr){
return seg[v];
}
int m=(l+r)/2;
push(v);
return min(get(l,m,2*v,cl,min(cr,m)),get(m+1,r,2*v+1,max(cl,m+1),cr));
}
lazymin(int n){
this->n=n;
seg.clear();
seg.resize(4*n+5);
lazy.clear();
lazy.resize(4*n+5,0);
build(1,n,1);
}
};
int sequence(int n, vector<int> a){
int ans=1;
lazymax segmax(n);
lazymin segmin(n);
vector<vector<int>> indices(n+1,vector<int>());
for(int i=0;i<n;i++){
indices[a[i]].pb(i+1);
}
for(int i=1;i<=n;i++){
for(int j:indices[i-1]){
segmax.update(1,n,1,j,n,-1);
segmin.update(1,n,1,j,n,-1);
}
for(int j:indices[i]){
segmax.update(1,n,1,j,n,-1);
segmin.update(1,n,1,j,n,-1);
}
if(indices[i].size()==0){
continue;
}
if(indices[i].size()==1){
continue;
}
int cnt=1;
int idx1=0;
int idx2=1;
int l=indices[i][idx1];
int r=indices[i][idx2];
//cout<<l<<' '<<r<<" ok what\n";
while(idx2<indices[i].size() and idx1<idx2){
int pl=segmax.get(1,n,1,1,l-1);
int ql=segmin.get(1,n,1,1,l-1);
int pr=segmax.get(1,n,1,r,n);
int qr=segmin.get(1,n,1,r,n);
int zero=0;
pl=max(pl,zero);
ql=min(ql,zero);
//cout<<pl<<' '<<ql<<' '<<pr<<' '<<qr<<" qerngoierng\n";
while(pr-ql>=idx1-idx2-1 and qr-pl<=idx2-idx1+1 and idx2<indices[i].size()){
//cout<<pl<<' '<<ql<<' '<<pr<<' '<<qr<<" qerwhyyyyyyyyyngoierng\n";
idx2++;
if(idx2==indices[i].size()){
break;
}
r=indices[i][idx2];
//cout<<idx1<<' '<<idx2<<' '<<r<<" what is happening\n";
pr=segmax.get(1,n,1,r,n);
qr=segmin.get(1,n,1,r,n);
}
idx2--;
r=indices[i][idx2];
//cout<<idx1<<' '<<idx2<<' '<<r<<" what is happening\n";
pr=segmax.get(1,n,1,r,n);
qr=segmin.get(1,n,1,r,n);
//cout<<l<<' '<<r<<" this works\n";
ans=max(ans,idx2-idx1+1);
idx1++;
l=indices[i][idx1];
}
}
return ans;
}
