#include "sequence.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (tl | 1)
int n;
struct SegmenTree {
int mn[MAXN << 2], mx[MAXN << 2], lazy[MAXN << 2];
void prop (int l, int r, int node) {
if (lazy[node] == 0) return;
if (l != r) {
lazy[tl] += lazy[node];
lazy[tr] += lazy[node];
}
mx[node] += lazy[node];
mn[node] += lazy[node];
lazy[node] = 0;
}
void pull (int l, int r, int node) {
mn[node] = min(mn[tl], mn[tr]);
mx[node] = max(mx[tl], mx[tr]);
}
void add (int l, int r, int a, int b, int c, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] += c;
prop(l, r, node);
return;
}
add(l, mid, a, b, c, tl);
add(mid + 1, r, a, b, c, tr);
pull(l, r, node);
}
int get_mx (int l, int r, int a, int b, int node) {
prop(l, r, node);
if (l > b || r < a) return -1e9;
if (l >= a && r <= b) return mx[node];
return max(get_mx(l, mid, a, b, tl), get_mx(mid + 1, r, a, b, tr));
}
int get_mn (int l, int r, int a, int b, int node) {
prop(l, r, node);
if (l > b || r < a) return 1e9;
if (l >= a && r <= b) return mn[node];
return min(get_mn(l, mid, a, b, tl), get_mn(mid + 1, r, a, b, tr));
}
} cur;
struct ImplicitSegmentTree {
vector <int> tree, lc, rc;
int cnt = 0;
void new_node () {
cnt++; tree.push_back(MAXN); lc.push_back(-1); rc.push_back(-1);
}
void init () {
tree.clear(); lc.clear(); rc.clear(); cnt = 0;
new_node();
}
void pull (int node) {
if (lc[node] != -1) tree[node] = min(tree[node], tree[lc[node]]);
if (rc[node] != -1) tree[node] = min(tree[node], tree[rc[node]]);
}
void update (int l, int r, int a, int b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] = min(tree[node], b);
return;
}
if (a <= mid) {
if (lc[node] == -1) {
new_node(); lc[node] = cnt - 1;
}
update(l, mid, a, b, lc[node]);
} else {
if (rc[node] == -1) {
new_node(); rc[node] = cnt - 1;
}
update(mid + 1, r, a, b, rc[node]);
}
pull(node);
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return MAXN;
if (l >= a && r <= b) return tree[node];
int mn = MAXN;
if (lc[node] != -1) {
mn = min(mn, get(l, mid, a, b, lc[node]));
}
if (rc[node] != -1) {
mn = min(mn, get(mid + 1, r, a, b, rc[node]));
}
return mn;
}
} dd;
int solve1 (vector <pair <int, int>> b) {
int mx = 0;
vector <array <int, 4>> events;
for (int i = 0; i < int(b.size()); i++) {
events.push_back({b[i].second, b[i].first, 1, i});
events.push_back({b[i].first, b[i].second, 0, i});
}
sort(events.begin(), events.end(), [&] (array <int, 4> x, array <int, 4> y) {
if (x[0] == y[0] && x[1] == y[1]) return x[2] < y[2];
if (x[0] == y[0]) return x[1] > y[1];
return x[0] < y[0];
});
dd.init();
for (int i = 0; i < int(events.size()); i++) {
if (events[i][2] == 0) {
dd.update(0, 4 * n, 2 * n + events[i][1], events[i][3], 0);
} else {
mx = max(mx, events[i][3] - dd.get(0, 4 * n, 2 * n + events[i][1], 4 * n, 0));
}
}
return mx;
}
int solve2 (vector <pair <int, int>> b) {
int mx = 0;
vector <array <int, 4>> events;
for (int i = 0; i < int(b.size()); i++) {
events.push_back({b[i].second, b[i].second + i, 1, i});
events.push_back({b[i].first, b[i].first + i, 0, i});
}
sort(events.begin(), events.end());
reverse(events.begin(), events.end());
dd.init();
for (int i = 0; i < int(events.size()); i++) {
int j = i;
while (j + 1 < int(events.size()) && events[j + 1][0] == events[i][0]) {
j++;
}
for (int k = i; k <= j; k++) {
if (events[k][2] == 1) {
mx = max(mx, events[k][3] - dd.get(0, 4 * n, 0, 2 * n + events[k][1], 0));
}
}
for (int k = i; k <= j; k++) {
if (events[k][2] == 0) {
dd.update(0, 4 * n, 2 * n + events[k][1], events[k][3], 0);
}
}
i = j;
}
return mx;
}
int solve3 (vector <pair <int, int>> b) {
int mx = 0;
vector <array <int, 4>> events;
for (int i = 0; i < int(b.size()); i++) {
events.push_back({b[i].first, b[i].first - i, 1, i});
events.push_back({b[i].second, b[i].second - i, 0, i});
}
sort(events.begin(), events.end());
dd.init();
for (int i = 0; i < int(events.size()); i++) {
int j = i;
while (j + 1 < int(events.size()) && events[j + 1][0] == events[i][0]) {
j++;
}
for (int k = i; k <= j; k++) {
if (events[k][2] == 1) {
mx = max(mx, events[k][3] - dd.get(0, 4 * n, 2 * n + events[k][1], 4 * n, 0));
}
}
for (int k = i; k <= j; k++) {
if (events[k][2] == 0) {
dd.update(0, 4 * n, 2 * n + events[k][1], events[k][3], 0);
}
}
i = j;
}
return mx;
}
int a[MAXN];
vector <int> occ[MAXN];
int sequence (int NB, vector <int> AB) {
n = NB;
for (int i = 1; i <= n; i++) {
occ[i].push_back(0);
}
for (int i = 1; i <= n; i++) {
a[i] = AB[i - 1];
occ[a[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
occ[i].push_back(n + 1);
}
for (int i = 1; i <= n; i++) {
cur.add(0, n, i, i, i, 1);
}
int mx = 0;
for (int i = 1; i <= n; i++) {
for (auto j : occ[i - 1]) {
cur.add(0, n, j, n, -1, 1);
}
for (auto j : occ[i]) {
cur.add(0, n, j, n, -1, 1);
}
vector <pair <int, int>> b;
for (int j = 0; j + 1 < int(occ[i].size()); j++) {
b.push_back({cur.get_mn(0, n, occ[i][j], occ[i][j + 1] - 1, 1), cur.get_mx(0, n, occ[i][j], occ[i][j + 1] - 1, 1)});
}
mx = max(mx, solve1(b));
mx = max(mx, solve2(b));
mx = max(mx, solve3(b));
}
return mx;
}
