#include "sequence.h"
#include <vector>
#include <bits/stdc++.h>
#include <bits/extc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;
using namespace __gnu_pbds;
#define pii pair<int,int>
#define fs first
#define sc second
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int mxn = 5e5+10;
vector<int> pos[mxn];
int N,ans;
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct node{
int mx,mn,tag;
node(){
mx = mn = tag = 0;
}
};
node seg[mxn*4];
void modify(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
seg[now].tag += v;
return;
}
if(mid>=s)modify(ls,l,mid,s,e,v);
if(mid<e)modify(rs,mid+1,r,s,e,v);
seg[now].mx = max(seg[ls].mx+seg[ls].tag,seg[rs].mx+seg[rs].tag);
seg[now].mn = min(seg[ls].mn+seg[ls].tag,seg[rs].mn+seg[rs].tag);
return;
}
int getmn(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now].mn+seg[now].tag;
if(mid>=e)return getmn(ls,l,mid,s,e)+seg[now].tag;
else if(mid<s)return getmn(rs,mid+1,r,s,e)+seg[now].tag;
else return min(getmn(ls,l,mid,s,e),getmn(rs,mid+1,r,s,e))+seg[now].tag;
}
int getmx(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now].mx+seg[now].tag;
if(mid>=e)return getmx(ls,l,mid,s,e)+seg[now].tag;
else if(mid<s)return getmx(rs,mid+1,r,s,e)+seg[now].tag;
else return max(getmx(ls,l,mid,s,e),getmx(rs,mid+1,r,s,e))+seg[now].tag;
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
bool intersect(pii a,pii b){
if(a.fs==b.fs)return true;
if(a.fs>b.fs)swap(a,b);
return a.sc>=b.fs;
}
void calc(vector<int> v){
if(v.empty())return;
for(int i = 0;i<v.size();i++){
seg.modify(0,0,N,v[i],N,-1);
}
v.insert(v.begin(),0);
v.push_back(N+1);
vector<pii> rng;
for(int i = 1;i<v.size();i++)rng.push_back(pii(seg.getmn(0,0,N,v[i-1],v[i]-1),seg.getmx(0,0,N,v[i-1],v[i]-1)));
auto pref = rng;
for(int i = 1;i<pref.size();i++){
pref[i].fs = min(pref[i].fs,pref[i-1].fs);
pref[i].sc = max(pref[i].sc,pref[i-1].sc);
}
int l = 0,r = rng.size()-1;
auto check = [&](int dis){
for(int i = dis;i<rng.size();i++){
auto ta = pref[i-dis],tb = rng[i];
tb.fs -= dis,tb.sc += dis;
if(intersect(ta,tb))return true;
}
return false;
};
while(l != r){
int mid = (l+r+1)>>1;
if(check(mid))l = mid;
else r = mid-1;
}
ans = max(ans,l);
for(int i = 1;i+1<v.size();i++){
seg.modify(0,0,N,v[i],N,-1);
}
return;
}
int sequence(int NN, std::vector<int> AA) {
N = NN;
for(int i = 0;i<N;i++)pos[AA[i]].push_back(i+1);
for(int i = 1;i<=N;i++)seg.modify(0,0,N,i,i,i);
ans = 0;
for(int i = 1;i<=N;i++)calc(pos[i]);
return ans;
}
