#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 5E5 + 2;
int t_mn[4 * N] , t_mx[4 * N];
int lzn[4 * N] , lzx[4 * N];
void push_mn(int u){
t_mn[u * 2] += lzn[u];
t_mn[u * 2 + 1] += lzn[u];
lzn[u * 2] += lzn[u];
lzn[u * 2 + 1] += lzn[u];
lzn[u] = 0;
}
void update_mn(int u , int l , int r , int L , int R , int x){
if(l > r || r < L || l > R){
return;
}
if(L <= l && r <= R){
t_mn[u] += x;
lzn[u] += x;
return;
}
int m = (l + r) / 2;
push_mn(u);
update_mn(u * 2 , l , m , L , R , x);
update_mn(u * 2 + 1 , m + 1 , r , L , R , x);
t_mn[u] = min(t_mn[u * 2] , t_mn[u * 2 + 1]);
}
int query_mn(int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return 1E9;
}
if(L <= l && r <= R){
return t_mn[u];
}
push_mn(u);
int m = (l + r) / 2;
return min(query_mn(u * 2 , l , m , L , R) , query_mn(u * 2 + 1 , m + 1 , r , L , R));
}
void push_mx(int u){
t_mx[u * 2] += lzx[u];
t_mx[u * 2 + 1] += lzx[u];
lzx[u * 2] += lzx[u];
lzx[u * 2 + 1] += lzx[u];
lzx[u] = 0;
}
void update_mx(int u , int l , int r , int L , int R , int x){
if(l > r || r < L || l > R){
return;
}
if(L <= l && r <= R){
t_mx[u] += x;
lzx[u] += x;
return;
}
int m = (l + r) / 2;
push_mx(u);
update_mx(u * 2 , l , m , L , R , x);
update_mx(u * 2 + 1 , m + 1 , r , L , R , x);
t_mx[u] = max(t_mx[u * 2] , t_mx[u * 2 + 1]);
}
int query_mx(int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return -1E9;
}
if(L <= l && r <= R){
return t_mx[u];
}
push_mx(u);
int m = (l + r) / 2;
return max(query_mx(u * 2 , l , m , L , R) , query_mx(u * 2 + 1 , m + 1 , r , L , R));
}
int sequence(int N, std::vector<int> a) {
for(int i = 0;i < 4 * (N + 1);i ++){
t_mn[i] = t_mx[i] = lzn[i] = lzx[i] = 0;
}
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) , mx(N + 1);
vector<int> pref_mn(N + 1) , pref_mx(N + 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_mn(1 , 1 , N + 1 , pos + 1 , N + 1 , x - mn[pos]);
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_mx(1 , 1 , N + 1 , pos + 1 , N + 1 , x - mx[pos]);
mx[pos] = x;
};
auto find_min = [&](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_mn(1 , 1 , N + 1 , L + 1 , R + 1);
};
auto find_max = [&](int L , int R){
// int best = pref_mx[L];
// for(int i = L;i <= R;i ++){
// best = max(best , pref_mx[i]);
// }
// return best;
return query_mx(1 , 1 , N + 1 , L + 1 , R + 1);
};
auto check = [&](int L , int R , int v){
int lmin = find_min(0 , L - 1);
int lmax = find_max(0 , L - 1);
int rmin = find_min(R , N);
int rmax = find_max(R , N);
int nR = find_min(R , R) , nL = find_min(L - 1 , L - 1);
int xR = find_max(R , R) , xL = find_max(L - 1 , L - 1);
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);
};
for(int i = 1;i <= N;i ++){
set_mn(i , +1);
set_mx(i , +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;
for(int i = 0;i < (int)t.size();i ++){
while(r + 1 < (int)t.size()){
++r;
set_mn(t[r] , 0);
set_mx(t[r] , 0);
if(!check(t[i] , t[r] , r - i + 1)){
set_mn(t[r] , -1);
set_mx(t[r] , +1);
--r;
break;
}
}
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;
}
