#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int mi, mx, lazy;
node(): mi(0), mx(0), lazy(0) {};
node(int _mi, int _mx): mi(_mi), mx(_mx), lazy(0) {};
};
const int maxn = 5e5 + 20;
int a[maxn];
vector<int> pos[maxn];
vector<int> pref[maxn][2];
vector<int> suf[maxn][2];
node tree[maxn * 4];
int n;
node merge(node L, node R) {
return node(min(L.mi, R.mi), max(L.mx, R.mx));
}
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = node(lt, lt);
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}
void push(int id) {
tree[id * 2].lazy += tree[id].lazy;
tree[id * 2].mi += tree[id].lazy;
tree[id * 2].mx += tree[id].lazy;
tree[id * 2 + 1].lazy += tree[id].lazy;
tree[id * 2 + 1].mi += tree[id].lazy;
tree[id * 2 + 1].mx += tree[id].lazy;
tree[id].lazy = 0;
}
void update(int id, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
tree[id].lazy -= 2;
tree[id].mi -= 2;
tree[id].mx -= 2;
return;
}
push(id);
int mt = (lt + rt) / 2;
if (qr <= mt) {
update(id * 2, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
update(id * 2 + 1, mt + 1, rt, ql, qr);
}
else {
update(id * 2, lt, mt, ql, mt);
update(id * 2 + 1, mt + 1, rt, mt + 1, qr);
}
tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}
node get(int id, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
return tree[id];
}
push(id);
int mt = (lt + rt) / 2;
if (qr <= mt) {
return get(id * 2, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
return get(id * 2 + 1, mt + 1, rt, ql, qr);
}
else {
return merge(get(id * 2, lt, mt, ql, mt), get(id * 2 + 1, mt + 1, rt, mt + 1, qr));
}
}
bool check(int k) {
for (int i = 1; i <= n; i++) {
for (int j = k - 1; j < (int)pos[i].size(); j++) {
if (suf[i][0][j] >= pref[i][0][j - (k - 1)] && suf[i][1][j] <= pref[i][1][j - (k - 1)]) {
return true;
}
}
}
return false;
}
int sequence(int _N, vector<int> _A) {
n = _N;
for (int i = 1; i <= n; i++) {
a[i] = _A[i - 1];
}
for (int i = 1; i <= n; i++) {
pos[a[i]].push_back(i);
}
build(1, 0, n);
for (int i = 1; i <= n; i++) {
for (auto p: pos[i]) {
pref[i][0].push_back(get(1, 0, n, 0, p - 1).mi);
suf[i][0].push_back(get(1, 0, n, p, n).mx);
}
for (auto p: pos[i]) {
update(1, 0, n, p, n);
}
for (auto p: pos[i]) {
pref[i][1].push_back(get(1, 0, n, 0, p - 1).mx);
suf[i][1].push_back(get(1, 0, n, p, n).mi);
}
}
int res = 1;
int lt = 1;
int rt = n;
while (lt <= rt) {
int mt = (lt + rt) / 2;
if (check(mt)) {
res = mt;
lt = mt + 1;
}
else {
rt = mt - 1;
}
}
return res;
}
