#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct Node {
int sum, pmax, pmin;
Node operator+(const Node &x) {
return {sum + x.sum, max(pmax, sum + x.pmax), min(pmin, sum + x.pmin)};
}
};
struct ST {
const int N;
vt<Node> st;
ST(const int n) : N(n), st(n << 1) {}
void update(int i, const int v) {
st[i += N] = {v, max(v, 0), min(v, 0)};
while (i >>= 1)
st[i] = st[i<<1] + st[i<<1|1];
}
Node query(int l, int r) {
Node L = {0, 0, 0}, R = {0, 0, 0};
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
L = L + st[l++];
if (r & 1)
R = st[--r] + R;
}
return L + R;
}
};
int sequence(int N, vt<int> A) {
vt<vt<int>> inds(N, {0});
FOR(i, 0, N-1)
inds[--A[i]].push_back(i + 1);
FOR(i, 0, N-1)
inds[i].push_back(N + 1);
ST st(N + 2);
FOR(i, 1, N)
st.update(i, 1);
int ans = 1;
FOR(x, 0, N-1) {
for (const auto &i : inds[x])
st.update(i, 0);
if (x)
for (const auto &i : inds[x-1])
st.update(i, -1);
vt<int> mx, mn;
int tot = 0;
FOR(i, 1, size(inds[x]) - 1) {
const Node v = st.query(inds[x][i-1] + 1, inds[x][i] - 1);
mx.push_back(tot + v.pmax);
mn.push_back(tot + v.pmin);
tot += v.sum;
}
FOR(i, 0, size(mx) - 1) {
int lo = 0, hi = i - 1;
while (lo < hi) {
const int mid = lo + hi >> 1;
if (mx[mid] + i >= mn[i] && i + mx[i] >= mn[mid])
hi = mid;
else
lo = mid + 1;
}
ans = max(ans, i - lo);
mx[i] -= i;
mn[i] += i;
if (i) {
mx[i] = max(mx[i], mx[i-1]);
mn[i] = min(mn[i], mn[i-1]);
}
}
}
return ans;
}
