#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];
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 Modify(int v, int l, int r, int ql, int qr, int x) {
if (l > r || l > qr || r < ql) {
return;
}
if (ql <= l && r <= qr) {
st[v].lzy += x;
st[v].mn += x;
st[v].mx += x;
push(v);
return;
}
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) {
if (l > r || l > qr || r < ql) {
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) {
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 sequence(int n, vector<int> a) {
for (int i = 0; i < n; i++) {
a[i]--;
}
vector<vector<int>> pos(n);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
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]);
pref_mx[j] = QueryMax(1, 0, n - 1, 0, pos[v][j]);
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;
}
