#include "sequence.h"
#include <algorithm>
#include <utility>
#include <vector>
using std::pair;
using std::vector;
constexpr int inf = 1 << 30;
struct segment_tree {
explicit segment_tree(const vector<int>& v) {
const int n = (int)v.size();
for (logn = 0; (1 << logn) < n; ++logn)
;
size = 1 << logn;
min.resize(2 * size);
max.resize(2 * size);
add.resize(size);
for (int i = 0; i < n; ++i) min[i + size] = max[i + size] = v[i];
for (int i = size - 1; i > 0; --i) fetch(i);
}
void range_add(int l, int r, int x) {
l += size, r += size;
push(l), push(r);
for (int s = l, t = r; s < t; s >>= 1, t >>= 1) {
if (s & 1) apply(s++, x);
if (t & 1) apply(--t, x);
}
pull(l), pull(r);
}
pair<int, int> fold(int l, int r) {
l += size, r += size;
push(l), push(r);
int s = +inf, t = -inf;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
s = std::min(s, min[l]);
t = std::max(t, max[l]);
l += 1;
}
if (r & 1) {
r -= 1;
s = std::min(s, min[r]);
t = std::max(t, max[r]);
}
}
return {s, t};
}
private:
int size, logn;
vector<int> min, max, add;
void apply(int i, int x) {
min[i] += x, max[i] += x;
if (i < size) add[i] += x;
}
void flush(int i) {
apply(2 * i + 0, add[i]);
apply(2 * i + 1, add[i]);
add[i] = 0;
}
void fetch(int i) {
min[i] = std::min(min[2 * i + 0], min[2 * i + 1]);
max[i] = std::max(max[2 * i + 0], max[2 * i + 1]);
}
void push(int i) {
const int rz = __builtin_ctz(i);
for (int k = logn; k > rz; --k) flush(i >> k);
}
void pull(int i) {
i >>= __builtin_ctz(i);
while (i >>= 1) fetch(i);
}
};
int sequence(int N, vector<int> A) {
vector<vector<int>> C(N);
for (int i = 0; i < N; ++i) {
A[i] -= 1;
C[A[i]].push_back(i);
}
int ret = 0;
for (int i = 0, j = 0; i < N; ++i) {
const int c = (int)C[i].size();
if (j <= N / 2 && N / 2 < j + c) ret = std::max(ret, c);
j += c;
}
vector<int> initial(N + 1);
for (int i = 0; i <= N; ++i) initial[i] = -i;
for (int phase = 0; phase < 2; ++phase) {
// segment_tree seg(initial);
// for (int x = 0; x < N; ++x) {
// const auto& v = C[x];
// const int n = (int)v.size();
// for (int i = 0, j = 0; i < n; i = j) {
// const auto [l0, r0] = seg.fold(0, v[i] + 1);
// while (j < n) {
// const auto [l1, r1] = seg.fold(v[j] + 1, N + 1);
// if (std::max(l0, l1) > std::min(r0, r1)) break;
// j += 1;
// }
// ret = std::max(ret, j - i);
// if (i == j) j += 1;
// }
// for (const int i : v) seg.range_add(i + 1, N + 1, 2);
// }
vector<int> a = initial;
for (int x = 0; x < N; ++x) {
const auto& v = C[x];
const int n = (int)v.size();
vector<int> cnt(N + 1);
for (const int i : v) cnt[i + 1] += 1;
for (int i = 0; i < N; ++i) cnt[i + 1] += cnt[i];
vector<int> lmin = a, rmin = a, lmax = a, rmax = a;
for (int i = 0; i < N; ++i) lmin[i + 1] = std::min(lmin[i + 1], lmin[i]);
for (int i = 0; i < N; ++i) lmax[i + 1] = std::max(lmax[i + 1], lmax[i]);
for (int i = N - 1; i >= 0; --i) rmin[i] = std::min(rmin[i], rmin[i + 1]);
for (int i = N - 1; i >= 0; --i) rmax[i] = std::max(rmax[i], rmax[i + 1]);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j <= N; ++j) {
if (std::max(lmin[i], rmin[j]) <= std::min(lmax[i], rmax[j])) {
ret = std::max(ret, cnt[j] - cnt[i]);
}
}
}
for (const int i : v) {
for (int j = i + 1; j <= N; ++j) a[j] += 2;
}
}
std::reverse(C.begin(), C.end());
}
return ret;
}
