#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
using namespace std;
const int M = 16e5 + 5, LIMN = 5e5 + 5;
const int INF = 1e9 + 7;
int n, seg[LIMN << 2][2];
int fen[M][2];
int lazy[LIMN << 2], ans = 1;
vector<int> P[LIMN];
vector<piii> L, R;
void build(int id, int l, int r){
if (l == r){
seg[id][0] = seg[id][1] = l;
return;
}
int mid = l + ((r - l) >> 1);
build(id << 1, l, mid); build((id << 1) | 1, mid + 1, r);
seg[id][0] = min(seg[id << 1][0], seg[(id << 1) | 1][0]);
seg[id][1] = max(seg[id << 1][1], seg[(id << 1) | 1][1]);
}
void down(int id){
int &v = lazy[id];
seg[id << 1][0] += v; seg[id << 1][1] += v;
seg[(id << 1) | 1][0] += v; seg[(id << 1) | 1][1] += v;
lazy[id << 1] += v; lazy[(id << 1) | 1] += v;
v = 0;
}
void update(int id, int l, int r, int u, int v, int val){
if (r < u || v < l) return;
if (u <= l && r <= v){
seg[id][0] += val;
seg[id][1] += val;
lazy[id] += val;
return;
}
if (lazy[id]) down(id);
int mid = l + ((r - l) >> 1);
update(id << 1, l, mid, u, v, val);
update((id << 1) | 1, mid + 1, r, u, v, val);
seg[id][0] = min(seg[id << 1][0], seg[(id << 1) | 1][0]);
seg[id][1] = max(seg[id << 1][1], seg[(id << 1) | 1][1]);
}
pii get(int id, int l, int r, int u, int v){
if (r < u || v < l) return {LIMN, -LIMN};
if (u <= l && r <= v) return {seg[id][0], seg[id][1]};
if (lazy[id]) down(id);
int mid = l + ((r - l) >> 1);
pii t1 = get(id << 1, l, mid, u, v),
t2 = get((id << 1) | 1, mid + 1, r, u, v);
return {min(t1.fi, t2.fi), max(t1.se, t2.se)};
}
void upfen(int x, int val, int k, bool t){
x += LIMN;
if (!k){
if (!t)
for (; x > 0; x -= x & -x)
fen[x][k] = min(fen[x][k], val);
else
for (; x > 0; x -= x & -x)
fen[x][k] = val;
} else {
if (!t)
for (; x <= n + LIMN; x += x & -x)
fen[x][k] = min(fen[x][k], val);
else
for (; x <= n + LIMN; x += x & -x)
fen[x][k] = val;
}
}
int gf(int x, int k){
int res = INF;
x += LIMN;
if (!k)
for (; x <= n + LIMN; x += x & -x)
res = min(res, fen[x][k]);
else
for (; x > 0; x -= x & -x)
res = min(res, fen[x][k]);
return res;
}
int sequence(int N, vector<int> A){
ios_base::sync_with_stdio(0); cin.tie(0);
n = N;
for (int i = 0; i < n; ++i) P[A[i]].push_back(i + 1);
build(1, 0, n);
for (int i = 1; i <= LIMN + n; ++i)
fen[i][0] = fen[i][1] = INF;
for (int i = 1; i <= n; ++i)
if ((int)P[i].size()){
for (int x: P[i])
update(1, 0, n, x, n, -1);
for (int k = 0; k < (int)P[i].size(); ++k){
pii x = get(1, 0, n, 0, P[i][k] - 1),
y = get(1, 0, n, P[i][k], n);
L.push_back({x, k}); R.push_back({y, k});
}
sort(L.begin(), L.end()); sort(R.begin(), R.end());
int j = 0;
for (piii x: R){
while (j < (int)L.size() && L[j].fi.fi <= x.fi.fi){
upfen(L[j].fi.se - (L[j].se - 1), L[j].se, 0, 0);
++j;
}
ans = max(ans, x.se - gf(x.fi.fi - x.se, 0) + 1);
}
for (int k = 0; k < j; ++k)
upfen(L[k].fi.se - (L[k].se - 1), INF, 0, 1);
j = (int)L.size() - 1;
for (int k = (int)R.size() - 1; k >= 0; --k){
piii x = R[k];
while (j >= 0 && L[j].fi.fi > x.fi.fi){
upfen(L[j].fi.fi + (L[j].se - 1), L[j].se, 1, 0);
--j;
}
ans = max(ans, x.se - gf(x.fi.se + x.se, 1) + 1);
}
for (int k = j + 1; k < (int)L.size(); ++k)
upfen(L[k].fi.fi + (L[k].se - 1), INF, 1, 1);
for (int x: P[i])
update(1, 0, n, x, n, -1);
L.clear(); R.clear();
}
return ans;
}
