#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 500005;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
int A[MAXN];
vector<int> V[MAXN];
struct node {
int s,e,m,lazy,mn,mx;
node *l, *r;
node (int _s, int _e){
s=_s;e=_e;m=(s+e)/2;
lazy=0;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
} else{
mn=-_s;mx=-_s;
}
}
void value(){
if(lazy==0)return;
if(s==e){
mn+=lazy;
mx+=lazy;
lazy=0;
return;
}
l->lazy+=lazy;
r->lazy+=lazy;
mn+=lazy;
mx+=lazy;
lazy=0;
return;
}
void update(int x, int y, int nval){
value();
if(s==x&&e==y){
lazy+=nval;
return;
}
if(x>m)r->update(x,y,nval);
else if(y<=m)l->update(x,y,nval);
else l->update(x,m,nval),r->update(m+1,y,nval);
l->value();r->value();
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
}
int query_min(int x, int y){
value();
if(s==x&&e==y)return mn;
if(x>m)return r->query_min(x,y);
else if(y<=m)return l->query_min(x,y);
else return min(l->query_min(x,m),r->query_min(m+1,y));
}
int query_max(int x, int y){
value();
if(s==x&&e==y)return mx;
if(x>m)return r->query_max(x,y);
else if(y<=m)return l->query_max(x,y);
else return max(l->query_max(x,m),r->query_max(m+1,y));
}
~node(){
if(s!=e){
delete l;
delete r;
}
}
}*seg;
bool check(int S){
seg=new node(0,n);
for(int v=1;v<=n;v++){
//pretend everything 0 is a -1
vector<int> idxes;
for(int i=0;i+S-1<(int)V[v].size();i++){
int st=V[v][i];
int en=V[v][i+S-1];
int Lval=seg->query_max(0,st-1);
int Rval=seg->query_min(en,n);
if(Rval<=Lval){
idxes.push_back(i);
}
}
for(auto x:V[v]){
seg->update(x,n,2);
}
// pretend every 0 is a +1
for(auto i:idxes){
int st=V[v][i];
int en=V[v][i+S-1];
int Lval=seg->query_min(0,st-1);
int Rval=seg->query_max(en,n);
if(Rval>=Lval){
delete seg;
return 1;
}
}
}
delete seg;
return 0;
}
int sequence(int N, std::vector<int> vec) {
n=N;
for(int i=1;i<=n;i++){
A[i]=vec[i-1];
}
for(int i=1;i<=n;i++){
V[A[i]].push_back(i);
}
int lo=0,hi=n+1;
while(lo<hi-1){
int mid=(lo+hi)/2;
if(check(mid))lo=mid;
else hi=mid;
}
return lo;
}
