#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())
const int inf = 10'000'000;
const int mx = 500'000;
int N;
vi A;
vi V;
struct sdata
{
int sm = 0;
int prefmin = 0;
int prefmax = 0;
int suffmin = 0;
int suffmax = 0;
sdata()
{
;
}
sdata(int V)
{
sm = V;
prefmin = min(V, 0);
suffmin = min(V, 0);
prefmax = max(V, 0);
suffmax = max(V, 0);
}
};
sdata combine(sdata a, sdata b)
{
sdata res;
res.sm = a.sm + b.sm;
res.prefmin = min(a.prefmin, a.sm + b.prefmin);
res.prefmax = max(a.prefmax, a.sm + b.prefmax);
res.suffmin = min(b.suffmin, b.sm + a.suffmin);
res.suffmax = max(b.suffmax, b.sm + a.suffmax);
return res;
}
struct segtree
{
int l;
int r;
sdata v;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
return;
int m = (l + r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void update(int I, int V)
{
if(l == r)
{
v = sdata(V);
}
else
{
if(I <= (l+r)/2)
left->update(I, V);
else
right->update(I, V);
v = combine(left->v, right->v);
}
}
sdata query(int L, int R)
{
if(R < L)
return sdata(0);
if(L <= l && r <= R)
return v;
else if(R <= (l+r)/2)
return left->query(L, R);
else if(L >= (l+r)/2 + 1)
return right->query(L, R);
else
return combine(left->query(L, R), right->query(L, R));
}
};
vvi val;
int sequence(int N_, vi A_)
{
N = N_;
A = vi{0};
for(int a : A_)
A.push_back(a);
vi lst[1+N];
for(int i = 1; i <= N; i++)
lst[A[i]].push_back(i);
segtree S(1, N);
for(int i = 1; i <= N; i++)
S.update(i, +1);
int res = 0;
for(int v = 1; v <= N; v++)
{
for(int i : lst[v])
S.update(i, 0);
for(int i : lst[v-1])
S.update(i, -1);
if(lst[v].empty())
continue;
// cerr << "\n\n\n";
// cerr << v << " : ";
// for(int u : lst[v])
// cerr << u << ' ';
// cerr << '\n';
// for(int i = 1; i <= N; i++)
// cerr << S.query(i, i).sm << ' ';
// cerr << '\n';
int H;
vi Z{0};
for(int i : lst[v])
Z.push_back(i);
H = sz(Z) - 1;
vector<sdata> dv(1 + H);
dv[0] = S.query(1, Z[1] - 1);
for(int i = 1; i < H; i++)
{
// cerr << i << " query = " << Z[i]+1 << ' ' << Z[i+1] - 1 << '\n';
dv[i] = S.query(Z[i] + 1, Z[i+1] - 1);
}
dv[H] = S.query(Z[H] + 1, N);
vi totsum(1 + H);
totsum[0] = 0;
for(int i = 1; i <= H; i++)
totsum[i] = totsum[i-1] + dv[i-1].sm;
/*
[1] l - 1 - totsum[l] + dv[l-1].suffmin <= r - dv[r].prefmin - totsum[r]
[2] l - 1 + totsum[l] - dv[l-1].suffmax <= r + totsum[r] + dv[r].prefmax
*/
// cerr << "hello!\n";
val = vvi(4, vi(1+H));
for(int i = 1; i <= H; i++)
{
val[0][i] = i - 1 - totsum[i] + dv[i-1].suffmin;
val[1][i] = i - dv[i].prefmin - totsum[i];
val[2][i] = i - 1 + totsum[i] - dv[i-1].suffmax;
val[3][i] = i + totsum[i] + dv[i].prefmax;
}
vpii lst1;
vpii lst2;
// cerr << "A\n";
for(int i = 1; i <= H; i++)
{
lst1.push_back({val[0][i], -i});
lst1.push_back({val[1][i], +i});
lst2.push_back({val[2][i], -i});
lst2.push_back({val[3][i], +i});
}
vi updpos(1+H), querpos(1+H);
sort(lst1.begin(), lst1.end());
sort(lst2.begin(), lst2.end());
// cerr << "B\n";
for(int i = 1; i <= sz(lst1); i++)
{
if(lst1[i-1].second < 0)
updpos[-lst1[i-1].second] = i;
else
querpos[lst1[i-1].second] = i;
}
vi bit(1+2*H, 1'000'000'000);
// cerr << "C\n";
for(pii pp : lst2)
{
if(pp.second < 0)
{
int i = -pp.second;
//update
for(int j = updpos[i]; j <= 2*H; j += j&-j)
bit[j] = min(bit[j], i);
}
else
{
int i = pp.second;
//query
for(int j = querpos[i]; j >= 1; j -= j&-j)
res = max(res, i - bit[j] + 1);
}
}
// cerr << "current res = " << res << '\n';
}
return res;
}
