#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);
}
};
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;
for(int i = 0;i<n;i++){
for(int s : pos[i]){
st.update(s,0);
}
for(int s = 0;s<pos[i].size();s++){
for(int e = pos[i].size()-1;e>s;e--){
int coun = e-s+1;
if(coun<=ans)
continue;
int lef = pos[i][s];
int rig = pos[i][e];
int sum = st.query(lef,rig)[4];
array<int,5> right = st.query(rig,n-1);
array<int,5> left = st.query(0,lef);
int premin = right[0];
int premax = right[1];
int sufmin = left[2];
int sufmax = left[3];
int lo = premin+sufmin+sum;
int hi = premax+sufmax+sum;
//cout << lef << " " << rig << " " << sum << " " << premin << " " << premax << " " << sufmin << " " << sufmax << "\n";
if(lo>coun||hi<-coun){
continue;
}
ans=max(ans,coun);
}
}
for(int s : pos[i]){
st.update(s,-1);
}
}
return ans;
}
