#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500050;
int ans = 1;
// if in range >= 0: segtree 1s = find min.
struct MaxSegTree {
int size = 1;
vector<int> seg, lazy;
void init(int n) {
while (size < n) size *= 2;
seg.assign(2 * size + 5, -1e9);
lazy.assign(2 * size + 5, 0);
}
void push(int id) {
seg[id] += lazy[id];
if (id < size) {
for (int i = 0; i < 2; i++) {
lazy[id * 2 + i] += lazy[id];
continue;
}
}
lazy[id] = 0;
}
void pull(int id) {
seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
void build(int l, int r, int id, vector<int>& v) {
if (l == r) {
seg[id] = v[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, id * 2, v);
build(mid + 1, r, id * 2 + 1, v);
pull(id);
}
void upd(int ql, int qr, int val, int l, int r, int id) {
push(id);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[id] = val;
push(id);
return;
}
int mid = (l + r) / 2;
upd(ql, qr, val, l, mid, id * 2);
upd(ql, qr, val, mid + 1, r, id * 2 + 1);
pull(id);
}
int qry(int ql, int qr, int l, int r, int id) {
push(id);
if (qr < l || r < ql) return -1e9;
if (ql <= l && r <= qr) return seg[id];
int mid = (l + r) / 2;
return max(qry(ql, qr, l, mid, id * 2), qry(ql, qr, mid + 1, r, id * 2 + 1));
}
} pref0, suff0;
struct MinSegTree {
int size = 1;
vector<int> seg, lazy;
void init(int n) {
while (size < n) size *= 2;
seg.assign(2 * size + 5, 1e9);
lazy.assign(2 * size + 5, 0);
}
void push(int id) {
seg[id] += lazy[id];
if (id < size) {
for (int i = 0; i < 2; i++) {
lazy[id * 2 + i] += lazy[id];
continue;
}
}
lazy[id] = 0;
}
void pull(int id) {
seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}
void build(int l, int r, int id, vector<int>& v) {
if (l == r) {
seg[id] = v[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, id * 2, v);
build(mid + 1, r, id * 2 + 1, v);
pull(id);
}
void upd(int ql, int qr, int val, int l, int r, int id) {
push(id);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[id] = val;
push(id);
return;
}
int mid = (l + r) / 2;
upd(ql, qr, val, l, mid, id * 2);
upd(ql, qr, val, mid + 1, r, id * 2 + 1);
pull(id);
}
int qry(int ql, int qr, int l, int r, int id) {
push(id);
if (qr < l || r < ql) return 1e9;
if (ql <= l && r <= qr) return seg[id];
int mid = (l + r) / 2;
return min(qry(ql, qr, l, mid, id * 2), qry(ql, qr, mid + 1, r, id * 2 + 1));
}
} pref1, suff1;
int n;
bool check(int l, int r, int c) {
int d = pref0.qry(r, r, 1, n, 1);
if (l > 1) d -= pref0.qry(l - 1, l - 1, 1, n, 1);
// cout << pref0.qry(r, r, 1, n, 1) << '\n';
// cout << d << '\n';
int w = d - c;
int x = 0, y = 0;
if (w <= 0) {
if (l > 1) {
int m = suff0.qry(l, l, 1, n, 1);
x = max(0, suff0.qry(1, l - 1, 1, n, 1) - m);
}
if (r < n) {
int m = pref0.qry(r, r, 1, n, 1);
y = max(0, pref0.qry(r + 1, n, 1, n, 1) - m);
}
}
else if (w >= 0) {
if (l > 1) {
int m = suff1.qry(l, l, 1, n, 1);
x = min(0, suff1.qry(1, l - 1, 1, n, 1) - m);
}
if (r < n) {
int m = pref1.qry(r, r, 1, n, 1);
y = min(0, pref1.qry(r + 1, n, 1, n, 1) - m);
}
}
// cout << w << ' ' << l << ' ' << r << ' ' << c << ' ' << x << ' ' << y << ' ';
if (w <= 0 && x + y + w + c >= 0) {
// cout << "true\n";
return true;
}
if (w >= 0 && x + y + w - c <= 0) {
// cout << "true\n";
return true;
}
// cout << "false\n";
return false;
}
int sequence(int _n, vector<int> tmp) {
n = _n;
vector<int> a(n+1), ps(n+1, 0);
vector<vector<int>> pos(n+1);
for (int i = 1; i <= n; i++) {
a[i] = tmp[i - 1];
pos[a[i]].push_back(i);
}
pref0.init(n + 1); suff0.init(n + 1);
pref1.init(n + 1); suff1.init(n + 1);
for (int i = 1; i <= n; i++) ps[i] = i;
pref0.build(1, n, 1, ps); pref1.build(1, n, 1, ps);
for (int i = 1; i <= n; i++) ps[i] = n - i + 1;
suff0.build(1, n, 1, ps); suff1.build(1, n, 1, ps);
for (int i = 1; i <= n; i++) {
int l = 0, r = 0;
for (int j = 0; j < pos[i].size(); j++) {
pref1.upd(pos[i][j], n, -2, 1, n, 1);
suff1.upd(1, pos[i][j], -2, 1, n, 1);
}
while (r < pos[i].size()) {
if (r < l || check(pos[i][l], pos[i][r], r - l + 1)) r++;
else l++;
ans = max(ans, r - l);
}
for (int j = 0; j < pos[i].size(); j++) {
pref0.upd(pos[i][j], n, -2, 1, n, 1);
suff0.upd(1, pos[i][j], -2, 1, n, 1);
}
// for (int j = 1; j <= n; j++) cout << pref0.qry(j, j, 1, n, 1) << ' ';
// cout << '\n';
}
return ans;
}
