#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
struct Node {
ll minP, maxP, minS, maxS, sum;
Node (ll val): minP(val), maxP(val), minS(val), maxS(val), sum(val) {}
Node operator+ (const Node &o) const {
Node ans(0);
ans.minP = min(minP, sum+o.minP);
ans.maxP = max(maxP, sum+o.maxP);
ans.minS = min(o.sum+minS, o.minS);
ans.maxS = max(o.sum+maxS, o.maxS);
ans.sum = sum+o.sum;
return ans;
};
};
vector <Node> tree;
ll n;
SegTree (ll n): tree(2*n, Node(0)), n(n) {}
void update (ll at, ll val) { update(at, val, 0, n-1, 0); }
void update (ll at, ll val, ll l, ll r, ll id) {
if (at <= l && r <= at) {
tree[id] = Node(val);
return;
}
if (at <= mid)
update(at, val, l, mid, id+1);
else
update(at, val, mid+1, r, id+off);
tree[id] = tree[id+1] + tree[id+off];
}
Node query (ll ql, ll qr) { return query(ql, qr, 0, n-1, 0) + Node(0); }
Node query (ll ql, ll qr, ll l, ll r, ll id) {
if (qr < l || r < ql) return Node(0);
if (ql <= l && r <= qr) return tree[id];
return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
}
};
int sequence (int n, vi ve) {
for (int &i : ve) i--;
vll idxs[n]{};
for (ll i = 0; i < n; i++) idxs[ve[i]].push_back(i);
ll ans = 0;
SegTree st(n);
for (ll i = 0; i < n; i++) {
st.update(i, 1);
}
cerr << boolalpha;
for (ll i = 0; i < n; i++) {
for (ll j : idxs[i]) st.update(j, 0);
ll l = 0, r = idxs[i].size();
while (l+1 < r) {
ll midd = (l+r)>>1;
bool val = false;
for (ll k = midd; k < idxs[i].size(); k++) {
ll sum = st.query(idxs[i][k-midd], idxs[i][k]).sum;
if (sum < 0) {
ll raise = st.query(0, idxs[i][k-midd]-1).maxS + st.query(idxs[i][k]+1, n-1).maxP;
sum += raise;
val |= sum >= -(midd+1);
} else {
ll drop = st.query(0, idxs[i][k-midd]-1).minS + st.query(idxs[i][k]+1, n-1).minP;
sum += drop;
val |= sum <= (midd+1);
}
}
if (val) {
l = midd;
} else {
r = midd;
}
}
ans = max(ans, l+1);
for (ll j : idxs[i]) st.update(j, -1);
}
return int(ans);
}
