#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int mn;
int mx;
int lzy;
};
const int MAX = 4e6;
node st[MAX];
int bal[MAX];
void push(int v) {
if (v * 2 + 1 < MAX) {
st[v * 2].lzy += st[v].lzy;
st[v * 2].mn += st[v].lzy;
st[v * 2].mx += st[v].lzy;
st[v * 2 + 1].lzy += st[v].lzy;
st[v * 2 + 1].mn += st[v].lzy;
st[v * 2 + 1].mx += st[v].lzy;
st[v].lzy = 0;
}
}
void pull(int v) {
st[v].mn = min(st[v * 2].mn, st[v * 2 + 1].mn);
st[v].mx = max(st[v * 2].mx, st[v * 2 + 1].mx);
}
void Build(int v, int l, int r) {
if (l == r) {
st[v].lzy = 0;
st[v].mn = 0;
st[v].mx = 0;
return;
}
int mid = l + r >> 1;
Build(v * 2, l, mid);
Build(v * 2 + 1, mid + 1, r);
}
void Modify(int v, int l, int r, int ql, int qr, int x) {
for (int i = ql; i <= qr; i++) {
bal[i] += x;
}
return;
if (l > r || l > qr || r < ql || ql > qr) {
return;
}
if (ql <= l && r <= qr) {
st[v].lzy += x;
st[v].mn += x;
st[v].mx += x;
push(v);
return;
}
push(v);
int mid = l + r >> 1;
Modify(v * 2, l, mid, ql, qr, x);
Modify(v * 2 + 1, mid + 1, r, ql, qr, x);
pull(v);
}
int QueryMax(int v, int l, int r, int ql, int qr) {
int res = (int) -1e9;
for (int i = ql; i <= qr; i++) {
res = max(res, bal[i]);
}
return res;
if (l > r || l > qr || r < ql || ql > qr) {
return (int) -1e9;
}
if (ql <= l && r <= qr) {
return st[v].mx;
}
push(v);
int mid = l + r >> 1;
int ans_l = QueryMax(v * 2, l, mid, ql, qr);
int ans_r = QueryMax(v * 2 + 1, mid + 1, r, ql, qr);
pull(v);
return max(ans_l, ans_r);
}
int QueryMin(int v, int l, int r, int ql, int qr) {
int res = (int) +1e9;
for (int i = ql; i <= qr; i++) {
res = min(res, bal[i]);
}
return res;
if (l > r || l > qr || r < ql) {
return (int) +1e9;
}
if (ql <= l && r <= qr) {
return st[v].mn;
}
push(v);
int mid = l + r >> 1;
int ans_l = QueryMin(v * 2, l, mid, ql, qr);
int ans_r = QueryMin(v * 2 + 1, mid + 1, r, ql, qr);
pull(v);
return min(ans_l, ans_r);
}
int BruteForce(int n, vector<int> a) {
int ans = 0;
for (int i = 0; i < n; i++) {
vector<int> f(n);
for (int j = 0; j < i; j++) {
f[j] = (a[j] <= a[i] ? -1 : +1);
}
for (int j = i + 1; j < n; j++) {
f[j] = (a[j] >= a[i] ? +1 : -1);
}
for (int j = 1; j < n; j++) {
f[j] += f[j - 1];
}
for (int l = 0; l < n; l++) {
int cnt = 0;
for (int r = l; r < n; r++) {
cnt += (a[r] == a[i]);
if (l <= i && i <= r && abs(f[r] - (l == 0 ? 0 : f[l - 1])) <= 1) {
ans = max(ans, cnt);
}
}
}
}
return ans;
}
int sequence(int n, vector<int> a) {
for (int i = 0; i < n; i++) {
a[i]--;
}
//return BruteForce(n, a);
vector<vector<int>> pos(n);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
for (int i = 0; i < MAX; i++) {
st[i].mn = (int) +1e9;
st[i].mx = (int) -1e9;
}
Build(1, 0, n - 1);
int ans = 0;
for (int i = 0; i < n; i++) {
Modify(1, 0, n - 1, i, n - 1, 1);
}
auto Intersect = [&](int l1, int r1, int l2, int r2) {
int L = max(l1, l2);
int R = min(r1, r2);
return L <= R;
};
for (int v = 0; v < n; v++) {
int sz = (int) pos[v].size();
vector<int> pref_mn(sz);
vector<int> pref_mx(sz);
vector<int> suff_mn(sz);
vector<int> suff_mx(sz);
for (int j = 0; j < sz; j++) {
Modify(1, 0, n - 1, pos[v][j], n - 1, -1);
pref_mn[j] = QueryMin(1, 0, n - 1, 0, pos[v][j] - 1);
pref_mx[j] = QueryMax(1, 0, n - 1, 0, pos[v][j] - 1);
suff_mn[j] = QueryMin(1, 0, n - 1, pos[v][j], n - 1);
suff_mx[j] = QueryMax(1, 0, n - 1, pos[v][j], n - 1);
pref_mn[j] = min(pref_mn[j], 0);
pref_mx[j] = max(pref_mx[j], 0);
Modify(1, 0, n - 1, pos[v][j], n - 1, -1);
}
for (int x = 0; x < sz; x++) {
for (int y = x; y < sz; y++) {
if (Intersect(suff_mn[y] - 1, suff_mx[y] + 1, pref_mn[x], pref_mx[x])) {
ans = max(ans, y - x + 1);
}
}
}
}
return ans;
}
