#include <bits/stdc++.h>
using namespace std;
vector<int> g[500005];
int lazy[2000005], hh = 1e9;
struct MED {
int x, y;
} t[2000005];
struct SEQ {
int num, x, y, z, t;
};
bool cmp(SEQ aa, SEQ bb) {
return aa.x < bb.x;
}
vector<SEQ> vv[500005];
MED Merge(MED aa, MED bb) {
MED res;
res.x = min(aa.x, bb.x);
res.y = max(aa.y, bb.y);
return res;
}
void push(int v) {
t[v << 1].x += lazy[v];
t[v << 1].y += lazy[v];
t[v << 1 | 1].x += lazy[v];
t[v << 1 | 1].y += lazy[v];
lazy[v << 1] += lazy[v];
lazy[v << 1 | 1] += lazy[v];
lazy[v] = 0;
}
void build(int v, int tl, int tr) {
lazy[v] = 0;
if (tl == tr) {
t[v] = {-tl, -tl};
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid);
build(v << 1 | 1, mid + 1, tr);
t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
void update(int v, int tl, int tr, int l, int r) {
if (l > r) return;
if (tl == l && tr == r) {
t[v].x += 2;
t[v].y += 2;
lazy[v] += 2;
return;
}
push(v);
int mid = (tl + tr) >> 1;
update(v << 1, tl, mid, l, min(r, mid));
update(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r);
t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
MED sum(int v, int tl, int tr, int l, int r) {
if (l > r) return {hh, -hh};
if (tl == l && tr == r) {
return t[v];
}
push(v);
int mid = (tl + tr) >> 1;
return Merge(sum(v << 1, tl, mid, l, min(r, mid)), sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
}
int tt[8000005], lazy2[8000005];
void push2(int v) {
if (lazy2[v] == 0) return;
tt[v << 1] = min(tt[v << 1], lazy2[v]);
tt[v << 1 | 1] = min(tt[v << 1 | 1], lazy2[v]);
lazy2[v << 1] = min(lazy2[v << 1], lazy2[v]);
lazy2[v << 1 | 1] = min(lazy2[v << 1 | 1], lazy2[v]);
lazy2[v] = 0;
}
void update2(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return;
if (tl == l && tr == r) {
tt[v] = min(tt[v], x);
lazy2[v] = min(lazy2[v], x);
return;
}
push2(v);
int mid = (tl + tr) >> 1;
update2(v << 1, tl, mid, l, min(r, mid), x);
update2(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x);
tt[v] = min(tt[v << 1], tt[v << 1 | 1]);
}
int sum2(int v, int tl, int tr, int l, int r) {
if (l > r) return hh;
if (tl == l && tr == r) {
return tt[v];
}
push2(v);
int mid = (tl + tr) >> 1;
return min(sum2(v << 1, tl, mid, l, min(r, mid)), sum2(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
}
map<int, int> mm;
int z = 0, res = 0, n;
void reset() {
z = 0;
for (auto &w : mm) w.second = ++z;
for (int j = 1; j <= z * 4; j++) {
tt[j] = hh;
lazy2[j] = 0;
}
for (int i = 1; i <= z; i++) vv[i].clear();
}
void trya(int i) {
if (g[i].empty()) return;
for (int w : g[i]) {
update(1, 0, n, w, n);
}
vector<pair<int, int>> v;
for (int j = 0; j < g[i].size(); j++) {
if (j == 0) {
v.push_back({0, g[i][j] - 1});
}
if (j != g[i].size() - 1) {
v.push_back({g[i][j], g[i][j + 1] - 1});
}
else v.push_back({g[i][j], n});
}
mm.clear();
int k = 0;
vector<SEQ> va;
for (auto &w : v) {
auto h = sum(1, 0, n, w.first, w.second);
mm[h.x] = mm[h.y] = mm[h.x - k] = mm[h.y - k] = 1;
k += 2;
}
reset();
k = 0;
for (auto &w : v) {
auto h = sum(1, 0, n, w.first, w.second);
int x = mm[h.x], y = mm[h.y], z = mm[h.x - k], t = mm[h.y - k];
k += 2;
vv[y].push_back({k / 2, x, y, z, t});
va.push_back({k / 2, x, y, z, t});
}
sort(va.begin(), va.end(), cmp);
int j = 0;
for (int i = 1; i <= z; i++) {
while (j < va.size() && va[j].x <= i) {
update2(1, 1, z, va[j].z, va[j].t, va[j].num);
j++;
}
for (auto w : vv[i]) {
res = max(res, w.num - sum2(1, 1, z, w.z, w.y));
}
}
}
int sequence(int N, vector<int> a) {
a.push_back(0);
n = N;
for (int i = n; i >= 1; i--) a[i] = a[i - 1];
a[0] = 0;
for (int i = 1; i <= n; i++) {
g[a[i]].push_back(i);
}
build(1, 0, n);
for (int i = 1; i <= n; i++) {
trya(i);
}
return res;
}
