// https://codeforces.com/blog/entry/116491?#comment-1031345
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
struct ST{
vector<pii> t;
vector<int> p;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
p.resize(4 * n);
}
void push(int v){
if (!p[v]) return;
int vv = 2 * v;
t[vv].ff += p[v];
t[vv].ss += p[v];
p[vv] += p[v];
t[vv + 1].ff += p[v];
t[vv + 1].ss += p[v];
p[vv + 1] += p[v];
p[v] = 0;
}
pii merge(pii x, pii y){
return {min(x.ff, y.ff), max(x.ss, y.ss)};
}
void add(int v, int tl, int tr, int l, int r, int x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
t[v].ff += x;
t[v].ss += x;
p[v] += x;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v);
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
t[v] = merge(t[vv], t[vv + 1]);
}
void add(int l, int r, int x){
add(1, 1, n, l, r, x);
}
pii get(int v, int tl, int tr, int l, int r){
if (l > tr || r < tl) return {1e9, -1e9};
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2, vv = 2 * v;
push(v);
return merge(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
}
pii get(int l, int r){
pii out = get(1, 1, n, l + !l, r);
if (!l){
out.ff = min(out.ff, 0);
out.ss = max(out.ss, 0);
}
return out;
}
};
struct FT{
vector<int> bit, h;
int n;
FT(int ns){
n = ns;
bit.assign(n + 1, 1e9);
}
void clear(){
for (int i: h){
bit[i] = 1e9;
}
h.clear();
}
void upd(int v, int x){
while (v <= n){
h.pb(v);
bit[v] = min(bit[v], x);
v |= (v + 1);
}
}
int get(int v){
int out = 1e9;
while (v > 0){
out = min(out, bit[v]);
v = (v & (v + 1)) - 1;
}
return out;
}
};
int sequence(int n, vector<int> a){
a.insert(a.begin(), 0);
vector<int> d[n + 1];
for (int i = 1; i <= n; i++) d[a[i]].pb(i);
ST T(n);
for (int i = 1; i <= n; i++) T.add(i, n, 1);
FT F(n);
vector<pii> all, c;
vector<arr3> f;
int out = 1;
for (int x = 1; x <= n; x++){
if (d[x].empty()) continue;
for (int j: d[x]) T.add(j, n, -1);
all.clear();
all.pb({0, d[x][0] - 1});
for (int i = 0; i + 1 < d[x].size(); i++){
all.pb({d[x][i], d[x][i + 1] - 1});
}
all.pb({d[x].back(), n});
for (auto &[l, r]: all){
pii f = T.get(l, r);
l = f.ff; r = f.ss;
}
f.clear();
for (int i = 0; i < all.size(); i++){
f.pb({i + all[i].ff, i - all[i].ss, -(i + 1)});
f.pb({i + all[i].ss, i - all[i].ff, i + 1});
}
auto cmp = [&](arr3 x, arr3 y){
if (x[0] != y[0]) return x[0] < y[0];
return x[2] < y[2];
};
sort(f.begin(), f.end(), cmp);
c.clear();
for (int i = 0; i < f.size(); i++){
c.pb({f[i][1], i});
}
sort(c.begin(), c.end());
int i = 0, cc = 0;
while (i < c.size()){
int j = i;
while (j < c.size() && c[i].ff == c[j].ff){
j++;
}
cc++;
while (i < j){
f[c[i].ss][1] = cc;
i++;
}
}
F.clear();
for (auto [x, y, ii]: f){
if (ii < 0){
ii = -ii - 1;
F.upd(y, ii);
continue;
}
ii--;
int t = F.get(y);
out = max(out, ii - t);
}
for (int j: d[x]) T.add(j, n, -1);
}
return out;
}
