#include "sequence.h"
#include <algorithm>
#include <utility>
#include <vector>
using std::pair;
using std::vector;
struct node {
int min, max, sum;
static node id() { return {0, 0, 0}; }
static node one(int x) { return {std::min(x, 0), std::max(x, 0), x}; }
node operator+(const node& n) const { return node(*this) += n; }
node& operator+=(const node& n) {
min = std::min(min, n.min + sum);
max = std::max(max, n.max + sum);
sum += n.sum;
return *this;
}
};
struct segment_tree {
explicit segment_tree(int n, const node& x) : size(n), data(2 * n, x) {
for (int i = n - 1; i > 0; --i) fetch(i);
}
void set(int i, const node& n) {
i += size;
data[i] = n;
while (i >>= 1) fetch(i);
}
node fold(int l, int r) {
l += size, r += size;
node ret_l = node::id(), ret_r = node::id();
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret_l += data[l++];
if (r & 1) ret_r = data[--r] + ret_r;
}
return ret_l + ret_r;
}
private:
int size;
vector<node> data;
void fetch(int i) { data[i] = data[2 * i + 0] + data[2 * i + 1]; }
};
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;
}
for (int phase = 0; phase < 2; ++phase) {
segment_tree seg(N, node::one(-1));
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) {
const auto [l0, r0, $0] = seg.fold(0, v[i]);
while (j < n) {
const int offset = seg.fold(0, v[j] + 1).sum;
const auto [l1, r1, $1] = seg.fold(v[j] + 1, N);
if (std::max(l0, l1 + offset) > std::min(r0, r1 + offset)) break;
j += 1;
}
ret = std::max(ret, j - i);
}
for (const int i : v) seg.set(i, node::one(+1));
}
std::reverse(C.begin(), C.end());
}
return ret;
}
