#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
struct DATA
{
int s = 0, mxp = 0, mxs = 0, mnp = 0, mns = 0;
};
const int MXN = 5e5 + 5;
DATA st[MXN << 2];
DATA combine(DATA x, DATA y)
{
return {x.s + y.s, max(x.mxp, x.s + y.mxp), max(y.mxs, y.s + x.mxs), min(x.mnp, x.s + y.mnp), min(y.mns, y.s + x.mns)};
}
void upd(int l, int r, int x, int ind, int val)
{
if (l == r)
{
st[x] = {val, max(0, val), max(0, val), min(0, val), min(0, val)};
return;
}
int mid = (l + r) >> 1;
if (ind <= mid) upd(l, mid, 2*x, ind, val);
else upd(mid + 1, r, 2*x + 1, ind, val);
st[x] = combine(st[2*x], st[2*x + 1]);
}
DATA get(int l, int r, int x, int lx, int rx)
{
if (lx > rx) return {0, 0, 0, 0, 0};
if (l > rx || r < lx) return {0, 0, 0, 0, 0};
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
int sequence(int N, vector<int> A)
{
vector<int> idx[N + 1];
for (int i = 0; i < N; i++) idx[A[i]].push_back(i);
for (int i = 0; i < N; i++) upd(0, N - 1, 1, i, 1);
int res = 0;
for (int val = 1; val <= N; val++)
{
vector<int> &v = idx[val];
for (int &i : v) upd(0, N - 1, 1, i, 1);
for (int r = 0, l = 0; r < v.size(); r++)
{
while (l <= r)
{
DATA x = get(0, N - 1, 1, v[l], v[r]);
// A = a, B = x - y
int A = r - l + 1;
int B = x.s;
DATA L = get(0, N - 1, 1, 0, v[l] - 1);
DATA R = get(0, N - 1, 1, v[r], N - 1);
int mn = B + L.mns + R.mnp, mx = B + L.mxs + R.mxp;
if ((mn <= 0 && 0 <= mx) || min(abs(mn), abs(mx)) <= A)
{
res = max(res, A);
break;
}
l++;
}
}
for (int &i : v) upd(0, N - 1, 1, i, -1);
}
return res;
}
/*
9
1 1 2 3 4 3 2 1 1
*/
