#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
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) , 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);
}
};
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);
}
};
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;
};
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;
};
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 val_min = (rmin - pref_mn[R]) + (pref_mx[R] - pref_mx[L - 1]) + (pref_mx[L - 1] - lmax);
int val_max = (rmax - pref_mx[R]) + (pref_mx[R] - pref_mx[L - 1]) + (pref_mn[L - 1] - 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;
}
