#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
//#define int long long
using namespace std;
const int N=5e5+5,M=5e4+5,inf=1e9,mod=1e9+7;
struct S{
pii seg[4*N];
int lazy[4*N];
void build(const int crr,const int l,const int r){
lazy[crr]=0;
if(l==r){
seg[crr]={-l,-l};
return;
}
const int mid=l+r>>1;
build(crr*2,l,mid);
build(crr*2+1,mid+1,r);
seg[crr]={min(seg[crr*2].fi,seg[crr*2+1].fi),max(seg[crr*2].se,seg[crr*2+1].se)};
}
void down(const int crr){
if(lazy[crr]){
const int x=lazy[crr]; lazy[crr]=0;
seg[crr*2].fi+=x; seg[crr*2+1].fi+=x;
seg[crr*2].se+=x; seg[crr*2+1].se+=x;
lazy[crr*2]+=x; lazy[crr*2+1]+=x;
}
}
void upd(const int crr,const int l,const int r,const int lm,const int rm){
if(l>rm || lm>r) return;
if(lm<=l && r<=rm){
seg[crr].fi+=2; seg[crr].se+=2;
lazy[crr]+=2;
return;
}
const int mid=l+r>>1;
down(crr);
upd(crr*2,l,mid,lm,rm);
upd(crr*2+1,mid+1,r,lm,rm);
seg[crr]={min(seg[crr*2].fi,seg[crr*2+1].fi),max(seg[crr*2].se,seg[crr*2+1].se)};
}
pii get(const int crr,const int l,const int r,const int lm,const int rm){
if(l>rm || lm>r) return {1e9,-1e9};
if(lm<=l && r<=rm) return seg[crr];
int mid=l+r>>1;
down(crr);
pii t1=get(crr*2,l,mid,lm,rm),g2=get(crr*2+1,mid+1,r,lm,rm);
return {min(t1.fi,g2.fi),max(t1.se,g2.se)};
}
} seg1,seg2;
bool check(const int l,const int r,const int n){
int mn=seg2.get(1,0,n,r,n).fi-seg2.get(1,0,n,0,l-1).se;
int mx=seg1.get(1,0,n,r,n).se-seg1.get(1,0,n,0,l-1).fi;
if(mn<=0 && mx>=0) return 1;
else return 0;
}
int sequence(int n, std::vector<int> a){
seg1.build(1,0,n);
seg2.build(1,0,n);
vector<int> pos[n+1];
int ans=1;
for(int i=0;i<n;i++){
pos[a[i]].push_back(i+1);
}
//<=x=1
//>x=-1
for(int i=1;i<=n;i++){
if(pos[i].empty()) continue;
for(auto j:pos[i]) seg1.upd(1,0,n,j,n);
int l=0;
for(int j=1;j<pos[i].size();j++){
while(!check(pos[i][l],pos[i][j],n)) l++;
ans=max(ans,j-l+1);
}
for(auto j:pos[i]) seg2.upd(1,0,n,j,n);
}
return ans;
}
//signed main(){
// //freopen("mushroom.inp","r",stdin);
// //freopen("mushroom.out","w",stdout);
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//// cout<<sequence(7, {1, 2, 3, 1, 2, 1, 3})<<"\n";
//// cout<<sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1})<<"\n";
//// cout<<sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2})<<"\n";
//}
