#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
struct node{
int mn, mx;
node(int mn=0, int mx=0) : mn(mn), mx(mx) {}
};
int n;
vector<vector<int>> pos;
vector<int> lazy;
vector<node> tr;
void change(int pos, int add) {
tr[pos].mn+=add;
tr[pos].mx+=add;
}
node pull(node L, node R) {
int mn, mx;
mn=min(L.mn, R.mn);
mx=max(L.mx, R.mx);
return node(mn, mx);
}
void push(int pos) {
lazy[2*pos+1]+=lazy[pos];
lazy[2*pos+2]+=lazy[pos];
change(2*pos+1, lazy[pos]);
change(2*pos+2, lazy[pos]);
lazy[pos]=0;
}
void update(int ll, int rr=n-1, int add=-1, int pos=0, int l=0, int r=n-1) {
if(ll>rr) return;
if(ll==l && rr==r) {change(pos, add); lazy[pos]+=add; return;}
push(pos); int mid=l+r>>1;
update(ll, min(rr, mid), add, 2*pos+1, l, mid);
update(max(mid+1, ll), rr, add, 2*pos+2, mid+1, r);
tr[pos]=pull(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
if(ll>rr) return node(INF, -INF);
if(ll==l && rr==r) return tr[pos];
push(pos); int mid=l+r>>1;
return pull(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
node build(int pos=0, int l=0, int r=n-1) {
lazy[pos]=0;
if(l==r) return tr[pos]=node(l+1, r+1);
int mid=l+r>>1;
return tr[pos]=pull(build(2*pos+1, l, mid), build(2*pos+2, mid+1, r));
}
bool can(int k) {
build();
for(int val=1; val<=n; val++) {
for(int p : pos[val]) update(p);
for(int i=0; i+k-1<pos[val].size(); i++) {
int l=pos[val][i], r=pos[val][i+k-1];
int temp=get(r, r).mn;
if(l) temp-=get(l-1, l-1).mx;
int need=abs(temp)-k;
if(need<=0) return 1;
int add=0;
if(l) {
if(temp<0) add=get(l-1, l-1).mn-get(0, l-1).mn;
else add=-get(l-1, l-1).mx+get(0, l-1).mx;
}
need-=add;
if(need<=0) return 1;
add=0;
if(r+1<n) {
if(temp<0) add=get(r+1, n-1).mx-get(r, r).mx;
else add=-get(r+1, n-1).mn+get(r, r).mn;
}
need-=add;
if(need<=0) return 1;
}
for(int p : pos[val]) update(p);
}
return 0;
}
int sequence(int N, vector<int> a) {
n=N;
pos.resize(n+1);
tr.resize(4*n);
lazy.resize(4*n);
for(int i=0; i<n; i++) pos[a[i]].push_back(i);
int l=1, r=n, ans=1;
while(l<=r) {
int mid=l+r>>1;
if(can(mid)) ans=mid, l=mid+1;
else r=mid-1;
}
return ans;
}
