#include "sequence.h"
#pragma GCC optimize("Ofast")
#include <vector>
#include <iostream>
#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) {
if (R == -1) return 0;
if (L > R) return 1e9;
return queryMi(0, 0, sz - 1, L, R);
}
int queryMx(int L, int R) {
if (R == -1) return 0;
if (L > R) return -1e9;
return queryMx(0, 0, sz - 1, L, R);
}
void print() {
int prev = 0;
for (int i = 0; i < sz; i++) {
int tmp = queryMx(i, i);
cout << tmp - prev << " ";
prev = tmp;
}
cout << endl;
}
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;
mod = 0;
}
};
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 cnt, int L, int R, vector < pair < int, int > >& s, vector < pair < int, int > >& p, vector < int >& pR, vector < int >& pL) {
int val = pR[R] - pL[L] - cnt;
pair < int, int > intr = { val - cnt, val + cnt };
intr.second += s[R].second;
intr.first += s[R].first;
intr.second += p[L].second;
intr.first += p[L].first;
return intr.first <= 0 && 0 <= intr.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) {
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;
vector < pair < int, int > > s(n), p(n);
vector < int > pL(n), pR(n);
for (auto x : values) {
for (auto i : ocr[x]) tmi.update(i, n - 1, -2);
//cout << x << endl;
//tmi.print();
//tmx.print();
for (auto i : ocr[x]) {
pR[i] = tmx.queryMx(i, i);
pL[i] = tmx.queryMx(i - 1, i - 1);
s[i].second = tmx.queryMx(i, n - 1) - pR[i];
s[i].first = tmi.queryMi(i, n - 1) - tmi.queryMi(i, i);
p[i].second = pL[i] - min(0, tmx.queryMi(0, i - 1));
p[i].first = tmi.queryMx(i - 1, i - 1) - max(0, tmi.queryMx(0, i - 1));
}
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, mid, ocr[x][i], ocr[x][i + mid - 1], s, p, pR, pL)) 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;
}
