#include <bits/stdc++.h>
struct segtree_mx {
int n, lgn;
std::vector<int> tr, mod;
void apply(int node, int x) {
tr[node] += x, mod[node] += x;
}
void push(int node) {
apply(node << 1, mod[node]);
apply(node << 1 | 1, mod[node]);
mod[node] = 0;
}
void pushall(int node) {
for (int k = lgn; k > 0; --k) {
push(node >> k);
}
}
void pull(int node) {
for (node >>= 1; node >= 1; node >>= 1) {
tr[node] = std::max(tr[node << 1], tr[node << 1 | 1]) + mod[node];
}
}
void update(int l, int r, int x) {
int cl = l += n, cr = r += n;
for (; l <= r; l >>= 1, r >>= 1) {
if (l & 1) apply(l++, x);
if (~r & 1) apply(r--, x);
}
pull(cl), pull(cr);
}
int get(int l, int r) {
int ret = INT_MIN;
for (pushall(l += n), pushall(r += n); l <= r; l >>= 1, r >>= 1) {
if (l & 1) ret = std::max(ret, tr[l++]);
if (~r & 1) ret = std::max(ret, tr[r--]);
}
return ret;
}
segtree_mx() = default;
segtree_mx(int n) : n(n), lgn(32 - __builtin_clz(n)), tr(2 * n, 0), mod(2 * n, 0) {}
};
struct segtree_mn {
segtree_mx tr;
segtree_mn() = default;
segtree_mn(int n) : tr(n) {}
void update(int l, int r, int x) {
tr.update(l, r, -x);
}
int get(int l, int r) {
return -tr.get(l, r);
}
};
int sequence(int n, std::vector<int> a) {
for (auto& i : a) --i;
int ans = 0;
segtree_mn mncur(n + 1), mnprev(n + 1);
segtree_mx mxcur(n + 1), mxprev(n + 1);
for (int i = 1; i <= n; ++i) {
mncur.update(i, n, 1);
mnprev.update(i, n, 1);
mxcur.update(i, n, 1);
mxprev.update(i, n, 1);
}
std::vector<std::vector<int>> occ(n);
for (int i = 0; i < n; ++i) occ[a[i]].push_back(i);
auto check = [&](int l, int r) -> bool {
int cprev = mxprev.get(r + 1, n) - mnprev.get(0, l);
int ccur = mncur.get(r + 1, n) - mxcur.get(0, l);
return ccur <= 0 && cprev >= 0;
};
for (int i = 0; i < n; ++i) {
for (auto x : occ[i]) {
mxcur.update(x + 1, n, -2);
mncur.update(x + 1, n, -2);
}
for (int l = 0, r = 0; l < occ[i].size(); ++i) {
while (r < occ[i].size() && check(occ[i][l], occ[i][r])) ++r;
ans = std::max(ans, r - l);
}
for (auto x : occ[i]) {
mxprev.update(x + 1, n, -2);
mnprev.update(x + 1, n, -2);
}
}
return ans;
}
// int main() {
// int n;
// std::cin >> n;
// std::vector<int> a(n);
// for (auto& i : a) std::cin >> i;
// std::cout << sequence(n, a);
// }
