#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct segTree{
//treat 0 as +-1, rest are either +1 or -1 fixed.
//store prefmin, prefmax, summin, summax, sufmin, sufmax
struct node{
int prefmin, prefmax, summin, summax, sufmin, sufmax;
};
node unite(node a, node b){
node ans;
ans.prefmin = min(a.prefmin,a.summin+b.prefmin);
ans.prefmax = max(a.prefmax,a.summax+b.prefmax);
ans.summin = a.summin+b.summin;
ans.summax = a.summax+b.summax;
ans.sufmin = min(b.sufmin,b.summin+a.sufmin);
ans.sufmax = max(b.sufmax,b.summax+a.sufmax);
return ans;
}
node *st;
node def;
void build(int l, int r, int ind){
if(l==r){
st[ind].summin=1;
st[ind].summax=1;
st[ind].prefmin=1;
st[ind].prefmax=1;
st[ind].sufmin=1;
st[ind].sufmax=1;
return;
}
int mid = (l+r)/2;
build(l,mid,ind*2+1);
build(mid+1,r,ind*2+2);
st[ind]=unite(st[ind*2+1],st[ind*2+2]);
}
int n;
segTree(int siz){
n=siz;
int x = ceil(log2(n));
x++;
st=new node[(1<<x)];
def.prefmin=inf;
def.sufmin=inf;
def.summin=0;
def.prefmax=-inf;
def.sufmax=-inf;
def.summax=0;
///initialize with 0s
build(0,n-1,0);
}
void update(int i, int val, int l=0, int r=-1, int ind=0){
if(r==-1)
r=n-1;
if(i<l||i>r)
return;
if(l==r){
if(val==0){
st[ind].summin=-1;
st[ind].summax=1;
st[ind].prefmin=-1;
st[ind].prefmax=1;
st[ind].sufmin=-1;
st[ind].sufmax=1;
}
else if(val==1){
st[ind].summin=1;
st[ind].summax=1;
st[ind].prefmin=1;
st[ind].prefmax=1;
st[ind].sufmin=1;
st[ind].sufmax=1;
}
else if(val==-1){
st[ind].summin=-1;
st[ind].summax=-1;
st[ind].prefmin=-1;
st[ind].prefmax=-1;
st[ind].sufmin=-1;
st[ind].sufmax=-1;
}
else{
assert(0);
}
return;
}
int mid = (l+r)/2;
update(i,val,l,mid,ind*2+1);
update(i,val,mid+1,r,ind*2+2);
st[ind]=unite(st[ind*2+1],st[ind*2+2]);
}
node query(int s, int e, int l=0, int r=-1, int ind=0){
if(r==-1)
r=n-1;
if(e<l||s>r){
return def;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return unite(query(s,e,l,mid,ind*2+1),query(s,e,mid+1,r,ind*2+2));
}
};
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);
int ans = 1;
for(int elem = 0;elem<n;elem++){
//set this elem to 0
for(int j : pos[elem]){
st.update(j,0);
}
int l = 0;
for(int r = 0;r<pos[elem].size();r++){
//check validity
segTree::node lef = st.query(0,pos[elem][l]);
segTree::node rig = st.query(pos[elem][r],n-1);
segTree::node mid = st.query(pos[elem][l],pos[elem][r]);
while(!(lef.sufmin+rig.prefmin+mid.summin+1+1<=0&&lef.sufmax+rig.prefmax+mid.summax-1-1>=0)){
//invalid
l++;
lef = st.query(0,pos[elem][l]);
rig = st.query(pos[elem][r],n-1);
mid = st.query(pos[elem][l],pos[elem][r]);
}
ans=max(ans,(r-l+1));
if(lef.sufmin+rig.prefmin+mid.summin+1+1<=0&&lef.sufmax+rig.prefmax+mid.summax-1-1>=0){
///this is valid
}
else{
assert(0);
}
}
for(int j : pos[elem]){
st.update(j,-1);
}
}
return ans;
}
