#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);
}*/
vector<vector<int>> pl(2),pr(2),ql(2),qr(2); //0 is for 1111 and 1 is for -1-1-1-1
for(int j=0;j<indices[i].size();j++){
int bruh=indices[i][j];
pl[0].pb(segmax.get(1,n,1,1,bruh-1));
ql[0].pb(segmin.get(1,n,1,1,bruh-1));
pr[0].pb(segmax.get(1,n,1,bruh,n));
qr[0].pb(segmin.get(1,n,1,bruh,n));
int zero=0;
pl[0][j]=max(pl[0][j],zero);
ql[0][j]=min(ql[0][j],zero);
}
for(int j:indices[i]){
segmax.update(1,n,1,j,n,-2);
segmin.update(1,n,1,j,n,-2);
}
for(int j=0;j<indices[i].size();j++){
int bruh=indices[i][j];
pl[1].pb(segmax.get(1,n,1,1,bruh-1));
ql[1].pb(segmin.get(1,n,1,1,bruh-1));
pr[1].pb(segmax.get(1,n,1,bruh,n));
qr[1].pb(segmin.get(1,n,1,bruh,n));
int zero=0;
pl[1][j]=max(pl[1][j],zero);
ql[1][j]=min(ql[1][j],zero);
}
if(indices[i].size()==0){
continue;
}
if(indices[i].size()==1){
continue;
}
/*cout<<i<< ": ka copium\n";
for(int j:pl[0]){
cout<<j<<' ';
}
cout<<'\n';
for(int j:pr[0]){
cout<<j<<' ';
}
cout<<'\n';
for(int j:ql[0]){
cout<<j<<' ';
}
cout<<'\n';
for(int j:qr[0]){
cout<<j<<' ';
}
cout<<'\n';*/
int lo=0,hi=indices[i].size();
while(lo<hi){
int mid=(lo+hi+1)/2;
bool flag=false;
for(int j=0;j+mid<=indices[i].size();j++){
if(pr[0][j+mid-1]>=ql[0][j] and qr[1][j+mid-1]<=pl[1][j]){
flag=true;
}
}
if(flag){
lo=mid;
}else{
hi=mid-1;
}
}
//cout<<lo<<'\n';
ans=max(ans,lo);
/*int cnt=1;
int idx1=0;
int idx2=0;
int l=indices[i][idx1];
int r=indices[i][idx2];
cout<<l<<' '<<r<<" ok what\n";
while(idx2<indices[i].size() and idx1<indices[i].size()){
if(idx1>idx2){
idx2=idx1;
}
l=indices[i][idx1];
r=indices[i][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 happening1\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];
cout<<idx1<<' '<<idx2<<" why is this not going in\n";
}*/
}
return ans;
}
