#include "sequence.h"
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;
class segmentTree {
public:
void build(int sz) {
this->sz = sz;
T.resize(4 * sz + 7);
}
void update(int L, int R, int x) {
update(0, 0, sz - 1, L, R, x);
}
int queryMi(int L, int R) {
return queryMi(0, 0, sz - 1, L, R);
}
int queryMx(int L, int R) {
return queryMx(0, 0, sz - 1, L, R);
}
private:
struct node {
int mi, mx;
int mod;
node() {
mi = 0; mx = 0;
mod = 0;
}
node(int mi, int mx) {
this->mi = mi;
this->mx = mx;
}
};
void apply(int val, int x) {
T[val].mi += x;
T[val].mx += x;
T[val].mod += x;
}
void push(int val, int tl, int tr) {
if (tl != tr && T[val].mod != 0) {
apply(2 * val + 1, T[val].mod);
apply(2 * val + 2, T[val].mod);
}
T[val].mod = 0;
}
node combine(node v1, node v2) {
return { min(v1.mi, v2.mi), max(v1.mx, v2.mx) };
}
int queryMi(int val, int tl, int tr, int L, int R) {
if (L <= tl && tr <= R) return T[val].mi;
if (tl > R || tr < L) return 1e9;
push(val, tl, tr);
int tm = (tl + tr) >> 1;
return min(queryMi(2 * val + 1, tl, tm, L, R), queryMi(2 * val + 2, tm + 1, tr, L, R));
}
int queryMx(int val, int tl, int tr, int L, int R) {
if (L <= tl && tr <= R) return T[val].mx;
if (tl > R || tr < L) return -1e9;
push(val, tl, tr);
int tm = (tl + tr) >> 1;
return max(queryMx(2 * val + 1, tl, tm, L, R), queryMx(2 * val + 2, tm + 1, tr, L, R));
}
void update(int val, int tl, int tr, int L, int R, int x) {
if (L <= tl && tr <= R) {
apply(val, x);
return;
}
if (tl > R || tr < L) return;
push(val, tl, tr);
int tm = (tl + tr) >> 1;
update(2 * val + 1, tl, tm, L, R, x);
update(2 * val + 2, tm + 1, tr, L, R, x);
T[val] = combine(T[2 * val + 1], T[2 * val + 2]);
}
int sz;
vector < node > T;
};
bool check(int n, int L, int R, segmentTree& tmi, segmentTree& tmx) {
pair < int, int > li, ri;
li.first = min(tmi.queryMi(0, L), 0);
li.second = max(tmx.queryMx(0, L), 0);
ri.first = tmi.queryMi(R, n - 1);
ri.second = tmx.queryMx(R, n - 1);
return max(li.first, ri.first) <= min(li.second, ri.second);
}
int bruteSequence(int n, vector < int > a) {
int res = 0;
for (int i = 0; i < n; i++) {
vector < int > tmp;
map < int, int > cnt;
for (int j = i; j < n; j++) {
tmp.push_back(a[j]);
cnt[a[j]]++;
sort(tmp.begin(), tmp.end());
res = max(res, cnt[tmp[(tmp.size() - 1) / 2]]);
res = max(res, cnt[tmp[(tmp.size()) / 2]]);
}
}
return res;
}
int sequence(int n, vector<int> a) {
return bruteSequence(n, a);
vector < int > values = a;
vector < vector < int > > ocr(n + 1);
for (int i = 0; i < n; i++) {
ocr[a[i]].push_back(i);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
segmentTree tmi, tmx;
tmi.build(n);
tmx.build(n);
for (int i = 0; i < n; i++) {
tmi.update(i, n - 1, 1);
tmx.update(i, n - 1, 1);
}
int res = 1;
for (auto x : values) {
for (auto i : ocr[x]) tmi.update(i, n - 1, -2);
int L = 1, R = ocr[x].size() + 1;
while (R - L > 1) {
int mid = (L + R) >> 1;
bool flag = false;
for (int i = 0; !flag && i + mid - 1 < ocr[x].size(); i++) {
if (check(n, ocr[x][i], ocr[x][i + mid - 1], tmi, tmx)) flag = true;
}
if (flag) L = mid;
else R = mid;
}
res = max(res, L);
for (auto i : ocr[x]) tmx.update(i, n - 1, -2);
}
return res;
}
