#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif // LOCAL
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const int inf = 1e9;
vector<int> a;
vector<vector<int>> pos;
struct Node {
int mn, mx;
Node() {}
Node(int _mn, int _mx) : mn(_mn), mx(_mx) {}
Node operator + (const Node& o) {
Node res;
res.mn = min(o.mn, mn);
res.mx = max(o.mx, mx);
return res;
}
Node operator + (int x) {
Node res = *this;
res.mn += x;
res.mx += x;
return res;
}
friend ostream& operator<<(ostream& os, Node p) {
return os << "(" << p.mn << "," << p.mx << ")"; }
};
struct SegTree {
int n;
vector<Node> st;
vector<int> lazy;
SegTree() {}
SegTree(int n) : n(n) {
st.resize(4 * n + 5, Node(inf, -inf));
lazy.resize(4 * n + 5, 0);
}
void build(int id, int l, int r) {
if (l == r) {
st[id].mn = l;
st[id].mx = l;
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = st[id * 2] + st[id * 2 + 1];
}
void update(int id, int l, int r, int u, int v, int x) {
if (u > r || v < l) return;
if (u <= l && r <= v) {
st[id].mn += x;
st[id].mx += x;
lazy[id] += x;
return;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, x);
update(id * 2 + 1, mid + 1, r, u, v, x);
st[id] = (st[id * 2] + st[id * 2 + 1]) + lazy[id];
}
Node get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return Node(inf, - inf);
if (u <= l && r <= v) return st[id];
int mid = (l + r) / 2;
return (get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v)) + lazy[id];
}
} st;
int sequence(int N, vector<int> A) {
int n = N;
assert(a.empty());
a.resize(n + 3, 0);
pos.resize(n + 3);
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1];
pos[a[i]].pb(i);
}
st = SegTree(n + 1);
st.build(1, 0, n);
int res = 0;
vector<Node> l1, l2, r1, r2;
for (int i = 1; i <= n; i++) {
l1.clear(), l2.clear(), r1.clear(), r2.clear();
// debug(pos[i]);
for (int j : pos[i]) {
l1.pb(st.get(1, 0, n, 0, j - 1));
r1.pb(st.get(1, 0, n, j, n));
}
for (int j : pos[i]) {
st.update(1, 0, n, j, n, - 2);
}
for (int j : pos[i]) {
l2.pb(st.get(1, 0, n, 0, j - 1));
r2.pb(st.get(1, 0, n, j, n));
}
// debug(l1, r1, l2, r2);
int l = 1;
int r = (int)pos[i].size();
while(l <= r) {
int mid = (l + r) / 2;
bool ok = 0;
for (int j = 0; j + mid - 1 < (int)pos[i].size(); j++) {
if (r1[j + mid - 1].mx - l1[j].mn >= 0 && r2[j + mid - 1].mn - l2[j].mx <= 0) {
ok = 1;
break;
}
}
if (ok) {
res = max(res, mid);
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
return res;
}
