#include <bits/stdc++.h>
#include "sequence.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
const int inf = 1e9;
int sequence(int n, vector<int> a) {
vector<int> gud[n + 1];
for (int i = 0; i <= n; i++) {
gud[i].push_back(-1);
}
for (int i = 0; i < n; i++) {
gud[a[i]].push_back(i);
}
for (int i = 0; i <= n; i++) {
gud[i].push_back(n);
}
int ans = 0;
for (int i = 0; i <= n; i++) {
int suf[n + 1]{};
for (int j = n - 1; j >= 0; j--) {
suf[j] = suf[j + 1] + (a[j] < i? -1 : 0) + (a[j] > i? 1 : 0);
}
array<int, 2> vl[SZ(gud[i]) - 1];
for (int j = 1; j < SZ(gud[i]) - 1; j++) {
vl[j] = {inf, -inf};
for (int k = gud[i][j - 1] + 1; k <= gud[i][j]; k++) {
vl[j][0] = min(vl[j][0], suf[k]);
vl[j][1] = max(vl[j][1], suf[k]);
}
}
for (int r = SZ(gud[i]) - 2; r >= 1; r--) {
array<int, 2> vr = {inf, -inf};
for (int k = gud[i][r] + 1; k <= gud[i][r + 1]; k++) {
vr[0] = min(vr[0], suf[k]);
vr[1] = max(vr[1], suf[k]);
}
for (int l = 1; l <= r; l++) {
if (vr[0] <= vl[l][0]) {
if (vl[l][0] + l <= r + vr[1] + 1) {
ans = max(ans, r - l + 1);
break;
}
} else {
if (l - vl[l][1] <= r - vr[0] + 1) {
ans = max(ans, r - l + 1);
}
}
}
}
}
return ans;
}
