#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
struct mnmx{
long long mn, mx;
mnmx() {}
mnmx(long long mn, long long mx) : mn(mn), mx(mx) {}
};
mnmx operator+(mnmx a, mnmx b) {
return mnmx(min(a.mn, b.mn), max(a.mx, b.mx));
}
struct Segment_tree{
struct Node{
long long l, r;
long long su = 0;
long long mn;
long long mx;
Node() {}
Node(long long ind, long long x) : l(ind), r(ind + 1), mn(min(0ll, x)), mx(max(0ll, x)), su(x) {}
Node(Node l, Node r) : l(l.l), r(r.r), su(l.su + r.su), mx(max(l.mx, l.su + r.mx)), mn(min(l.mn, l.su + r.mn)) {}
};
vector<Node> tr;
void build(long long i, long long l, long long r, long long fill) {
if (r - l == 1) {
tr[i] = Node(l, fill);
return;
}
long long m = (l + r) / 2;
build(2 * i + 1, l, m, fill);
build(2 * i + 2, m, r, fill);
tr[i] = Node(tr[2 * i + 1], tr[2 * i + 2]);
}
void upd(long long ind, long long x, long long i = 0) {
if (ind < tr[i].l || ind >= tr[i].r) return;
if (tr[i].r - tr[i].l == 1) {
tr[i] = Node(ind, x);
return;
}
upd(ind, x, 2 * i + 1);
upd(ind, x, 2 * i + 2);
tr[i] = Node(tr[2 * i + 1], tr[2 * i + 2]);
}
Node get(long long l, long long r, long long i = 0) {
if (l >= r) return Node(l, 0);
if (l <= tr[i].l && tr[i].r <= r) {
return tr[i];
}
if ((tr[i].l + tr[i].r) / 2 <= l) return get(l, r, 2 * i + 2);
if ((tr[i].l + tr[i].r) / 2 >= r) return get(l, r, 2 * i + 1);
return Node(get(l, r, 2 * i + 1), get(l, r, 2 * i + 2));
}
Node get2(long long l, long long r) {
auto ans1 = get(l, r);
auto ans2 = get(0, l);
ans1.mn += ans2.su;
ans1.mx += ans2.su;
return ans1;
}
Segment_tree(long long n, long long fill = -1) {
tr.resize(4 * n);
build(0, 0, n, fill);
}
};
bool check(long long mid, vector<mnmx> a) {
mnmx cur = mnmx(a.back().mn + 1, a.back().mx - 1);
for (long long i = a.size() - mid - 1; i >= 0; i--) {
cur = mnmx(cur.mn - 1, cur.mx + 1) + a[i + mid];
if ((a[i].mx + mid) < cur.mn || cur.mx < (a[i].mn - mid)) continue;
return true;
}
return false;
}
int sequence(int n, vector<int> a) {
long long fans = 1;
vector<vector<long long>> cnt(n);
for (long long i = 0; i < n; i++) {
a[i]--;
cnt[a[i]].push_back(i);
}
Segment_tree tr(n);
for (auto &i : cnt) {
if (i.size() < 2) {
for (auto &j : i) tr.upd(j, 1);
continue;
}
long long m = i.size();
for (auto &j : i) {
tr.upd(j, 0);
}
vector<mnmx> pref, a;
long long p = 0;
for (auto &j : i) {
auto tmp = tr.get2(p, j);
auto tmp2 = mnmx(tmp.mn, tmp.mx);
a.push_back(tmp2);
p = j;
}
auto tmp = tr.get2(p, n);
auto tmp2 = mnmx(tmp.mn, tmp.mx);
a.push_back(tmp2);
long long l = 1, r = m + 1;
while (r - l > 1) {
long long mid = (l + r) / 2;
if (check(mid, a)) {
l = mid;
} else {
r = mid;
}
}
fans = max(fans, l);
for (auto &j : i) {
tr.upd(j, 1);
}
}
return fans;
}
