#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
struct SegmentTree {
int n;
vector<int> t;
SegmentTree(int _n) {
n = _n;
t.resize(4 * n);
}
void update(int id, int tl, int tr, int i, int v) {
if (tl == tr) {
t[id] += v;
return;
}
int x = 2 * id + 1, y = x + 1, tm = (tl + tr) / 2;
if (i <= tm) {
update(x, tl, tm, i, v);
} else {
update(y, tm + 1, tr, i, v);
}
t[id] = t[x] + t[y];
}
int sum(int id, int tl, int tr, int i) {
if (tl == tr) return t[id];
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm) return sum(x, tl, tm, i);
else return sum(y, tm + 1, tr, i);
}
int get(int id, int tl, int tr, int k) {
if (tl == tr) {
return tl;
}
int x = 2 * id + 1, y = x + 1, tm = (tl + tr) / 2;
if (t[x] > k) {
return get(x, tl, tm, k);
} else {
return get(y, tm + 1, tr, k - t[x]);
}
}
void update(int i, int v) { update(0, 0, n - 1, i, v); }
int get(int k) { return get(0, 0, n - 1, k); }
};
int sequence(int n, vector<int> a) {
vector<vector<int>> pos(n + 1);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
int ans = 0;
for (int l = 0; l < n; l++) {
SegmentTree t(n + 1);
for (int r = l; r < n; r++) {
t.update(a[r], 1);
int m = t.get((r - l + 1) / 2);
int tr = ranges::upper_bound(pos[m], r) - pos[m].begin();
int tl = ranges::lower_bound(pos[m], l) - pos[m].begin();
ans = max(ans, tr - tl);
if ((r - l + 1) % 2 == 0) {
m = t.get((r - l) / 2);
tr = ranges::upper_bound(pos[m], r) - pos[m].begin();
tl = ranges::lower_bound(pos[m], l) - pos[m].begin();
ans = max(ans, tr - tl);
}
}
}
return ans;
}
