#include "sequence.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<array<int,2>,null_type,less<array<int,2>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
struct segTree{
//{prefmin,prefmax,sufmin,sufmax,sum}
array<int,5> *st;
array<int,5>def;
int n;
segTree(int siz){
int x = ceil(log2(siz));
x++;
st=new array<int,5>[(1<<x)];
n=siz-1;
def={0,0,0,0,0};
fill(st,st+(1<<x),def);
}
array<int,5> unite(array<int,5> lef, array<int,5> rig){
array<int,5>ans;
ans[0]=min(lef[0],lef[4]+rig[0]);
ans[1]=max(lef[1],lef[4]+rig[1]);
ans[2]=min(rig[2],rig[4]+lef[2]);
ans[3]=max(rig[3],rig[4]+lef[3]);
ans[4]=lef[4]+rig[4];
return ans;
}
void rupdate(int l, int r, int ind, int i, int val){
if(i<l||i>r){
return;
}
if(l==r){
st[ind]={val,val,val,val,val};
return;
}
int mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i,val);
rupdate(mid+1,r,ind*2+2,i,val);
st[ind] = unite(st[ind*2+1],st[ind*2+2]);
}
void update(int i, int val){
rupdate(0,n,0,i,val);
}
array<int,5>rquery(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return def;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return unite(rquery(l,mid,s,e,ind*2+1),rquery(mid+1,r,s,e,ind*2+2));
}
array<int,5>query(int l, int r){
return rquery(0,n,l,r,0);
}
};
bool check(int x, array<int,5>nums[], int n, vector<int>(&pos)[]){
for(int o = 0;o<n;o++){
for(int i = 0;i<=((int)pos[o].size())-x;i++){
int j = i+x-1;
int oi = i;
int oj = j;
i=pos[o][i];
j=pos[o][j];
int sum = nums[j][4]-nums[i][4];
int mn = nums[j][2]+nums[i][0];
int mx = nums[j][3]+nums[i][1];
int lo = mn+sum;
int hi = mx+sum;
i=oi;
j=oj;
if(lo>x||hi<-x){
continue;
}
return 1;
}
}
return 0;
}
int sequence(int n, vector<int> arr) {
vector<int>pos[n];
for(int i = 0;i<n;i++){
arr[i]--;
pos[arr[i]].push_back(i);
}
segTree st(n);
for(int i = 0;i<n;i++){
st.update(i,1);
}
int ans = 1;
array<int,5>nums[n];
//lefmin,lefmax,rigmin,rigmax,sum
for(int i = 0;i<n;i++){
for(int ind : pos[i]){
array<int,5>pre = st.query(0,ind);
array<int,5>suf = st.query(ind,n-1);
nums[ind][0]=pre[2];
nums[ind][2]=suf[0];
}
for(int s : pos[i]){
st.update(s,-1);
}
int cn = 0;
for(int ind : pos[i]){
cn++;
array<int,5>pre = st.query(0,ind);
array<int,5>suf = st.query(ind,n-1);
nums[ind][1]=pre[3];
nums[ind][3]=suf[1];
nums[ind][4]=pre[4]+cn;
}
}
int lo = 1;
int hi = n;
while(lo<hi){
int mid = (lo+hi+1)/2;
if(check(mid,nums,n,pos)){
lo=mid;
}
else{
hi=mid-1;
}
}
return lo;
}
