#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 5e5+5;
const string NAME = "";
struct ST{
int MIN,MAX,lazy=0;
inline void add(int val){
MIN+=val, MAX+=val, lazy+=val;
}
inline void combine(const ST& a, const ST& b){
MIN=min(a.MIN,b.MIN), MAX=max(a.MAX,b.MAX);
}
}sgt[MAXN<<2];
vector<int> pos[MAXN];
void build(int id, int l, int r){
if(l==r) return sgt[id].MIN=sgt[id].MAX=l, void();
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
sgt[id].combine(sgt[id<<1],sgt[id<<1|1]);
}
inline void down(int id){
sgt[id<<1].add(sgt[id].lazy), sgt[id<<1|1].add(sgt[id].lazy);
sgt[id].lazy=0;
}
void update(int id, int l, int r, int u, int v, int val){
if(v<l||r<u) return;
if(u<=l&&r<=v){
sgt[id].MIN+=val, sgt[id].MAX+=val, sgt[id].lazy+=val;
return;
}
down(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
sgt[id].combine(sgt[id<<1],sgt[id<<1|1]);
}
pair<int,int> get(int id, int l, int r, int u, int v){
if(v<l||r<u) return {1e9,-1e9};
if(u<=l&&r<=v) return {sgt[id].MIN,sgt[id].MAX};
int mid=(l+r)>>1;
pair<int,int> L=get(id<<1,l,mid,u,v), R=get(id<<1|1,mid+1,r,u,v);
return {min(L.fi,R.fi),max(L.se,R.se)};
}
bool intersect(pair<int,int> a, pair<int,int> b, int len){
b.fi-=len, b.se+=len;
return (a.se>=b.fi&&b.se>=a.fi);
}
int sequence(int n, vector<int> a){
for(int i = 0; i<n; ++i)
pos[a[i]].pb(i+1);
build(1,0,n);
int rs=0;
for(int med = 1; med<=n; ++med){
for(int& i : pos[med])
update(1,0,n,i,n,-1);
for(int i=0, j=0; i<sz(pos[med]); ++i){
if(j<i) j=i;
while(j<sz(pos[med])&&intersect(get(1,0,n,0,pos[med][i]-1),get(1,0,n,pos[med][j],n),j-i+1)) rs=max(rs,j-i+1), ++j;
}
for(int& i : pos[med])
update(1,0,n,i,n,-1);
}
return rs;
}
//int main()
//{
// tt;
// if(fopen((NAME + ".INP").c_str(), "r")) fo;
// int n;
// vector<int> a;
// cin >> n;
// a.resize(n);
// for(int i = 0; i<n; ++i)
// cin >> a[i];
// cout << sequence(n,a);
//}
