#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 5E5 + 2;
struct node{
int mx , mn , lz0 = 0 , lz1 = 0;
} t[4 * N];
node neut = {(int)-1E9 , (int)1E9 , 0 , 0};
node join(node x , node y){
node z;
z.mx = max(x.mx , y.mx);
z.mn = min(x.mn , y.mn);
return z;
}
void build(int u , int l , int r){
if(l == r){
t[u].mx = t[u].mn = r - 1;
return;
}
int m = (l + r) / 2;
build(u * 2 , l , m);
build(u * 2 + 1 , m + 1 , r);
t[u] = join(t[u * 2] , t[u * 2 + 1]);
}
void push(int u){
t[u * 2].mn += t[u].lz0;
t[u * 2 + 1].mn += t[u].lz0;
t[u * 2].lz0 += t[u].lz0;
t[u * 2 + 1].lz0 += t[u].lz0;
t[u].lz0 = 0;
t[u * 2].mx += t[u].lz1;
t[u * 2 + 1].mx += t[u].lz1;
t[u * 2].lz1 += t[u].lz1;
t[u * 2 + 1].lz1 += t[u].lz1;
t[u].lz1 = 0;
}
void update(int u , int l , int r , int L , int R , int x , int w){
if(l > r || r < L || l > R){
return;
}
if(L <= l && r <= R){
if(w == 0){
t[u].mn += x;
t[u].lz0 += x;
}else{
t[u].mx += x;
t[u].lz1 += x;
}
return;
}
push(u);
int m = (l + r) / 2;
update(u * 2 , l , m , L , R , x , w);
update(u * 2 + 1 , m + 1 , r , L , R , x , w);
t[u] = join(t[u * 2] , t[u * 2 + 1]);
}
node query(int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return neut;
}
if(L <= l && r <= R){
return t[u];
}
push(u);
int m = (l + r) / 2;
return join(query(u * 2 , l , m , L , R) , query(u * 2 + 1 , m + 1 , r , L , R));
}
int sequence(int N, std::vector<int> a) {
vector<int> A(N + 1);
for(int i = 1;i <= N;i ++){
A[i] = a[i - 1];
}
vector<vector<int>> occ(N + 1);
for(int i = 1;i <= N;i ++){
occ[A[i]].emplace_back(i);
}
vector<int> mn(N + 1 , +1) , mx(N + 1 , +1);
auto set_mn = [&](int pos , int x){
// mn[pos] = x;
// for(int i = 0;i <= N;i ++){
// pref_mn[i] = mn[i] + (i > 0 ? pref_mn[i - 1] : 0);
// }
update(1 , 1 , N + 1 , pos + 1 , N + 1 , x - mn[pos] , 0);
mn[pos] = x;
};
auto set_mx = [&](int pos , int x){
// mx[pos] = x;
// for(int i = 0;i <= N;i ++){
// pref_mx[i] = mx[i] + (i > 0 ? pref_mx[i - 1] : 0);
// }
update(1 , 1 , N + 1 , pos + 1 , N + 1 , x - mx[pos] , 1);
mx[pos] = x;
};
auto get= [&](int L , int R){
// int best = pref_mn[L];
// for(int i = L;i <= R;i ++){
// best = min(best , pref_mn[i]);
// }
// return best;
return query(1 , 1 , N + 1 , L + 1 , R + 1);
};
auto check = [&](int L , int R , int v){
node dL = get(0 , L - 1);
int lmin = dL.mn , lmax = dL.mx;
node dR = get(R , N);
int rmin = dR.mn , rmax = dR.mx;
node onL = get(L - 1 , L - 1);
int nL = onL.mn , xL = onL.mx;
node onR = get(R , R);
int nR = onR.mn , xR = onR.mx;
int val_min = (rmin - nR) + (nR - nL) + (xL - lmax);
int val_max = (rmax - xR) + (xR - xL) + (nL - lmin);
return !(val_max < -v || v < val_min);
};
build(1 , 1 , N + 1);
int ans = 0;
for(int v = 1;v <= N;v ++){
auto &t = occ[v];
for(int x : t){
set_mn(x , -1);
}
int r = -1;
bool is_done = false;
for(int i = 0;i < (int)t.size();i ++){
while(r + 1 < (int)t.size()){
++r;
if(!is_done){
set_mn(t[r] , 0);
set_mx(t[r] , 0);
is_done = true;
}
if(!check(t[i] , t[r] , r - i + 1)){
--r;
break;
}
is_done = false;
}
ans = max(ans , r - i + 1);
set_mn(t[i] , -1);
set_mx(t[i] , +1);
}
for(int x : t){
//set_mn(x , -1);
set_mx(x , -1);
}
}
return ans;
}
