#include "sequence.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int infinity = 1e9;
struct Seg{
int n;
vii seg;
vi add;
Seg() {}
Seg(int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n);
add.resize(2 * n);
}
inline void pull(int i) {
seg[i].x = min(seg[i << 1].x, seg[i << 1 | 1].x);
seg[i].y = max(seg[i << 1].y, seg[i << 1 | 1].y);
}
inline void push(int i) {
add[i << 1] += add[i];
seg[i << 1].x += add[i], seg[i << 1].y += add[i];
add[i << 1 | 1] += add[i];
seg[i << 1 | 1].x += add[i], seg[i << 1 | 1].y += add[i];
add[i] = 0;
}
void update(int a, int b, int x, int ind, int l, int r) {
if (a <= l && r <= b) {
add[ind] += x;
seg[ind].x += x, seg[ind].y += x;
return;
}
if (r <= a || b <= l) return;
push(ind);
update(a, b, x, ind << 1, l, (l + r) >> 1);
update(a, b, x, ind << 1 | 1, (l + r) >> 1, r);
pull(ind);
}
inline void update(int a, int b, int x) {
update(a, b, x, 1, 0, n);
}
pii query(int a, int b, int ind, int l, int r) {
if (a <= l && r <= b) return seg[ind];
if (r <= a || b <= l) return {infinity, -infinity};
push(ind);
pii p1 = query(a, b, ind << 1, l, (l + r) >> 1);
pii p2 = query(a, b, ind << 1 | 1, (l + r) >> 1, r);
return {min(p1.x, p2.x), max(p1.y, p2.y)};
}
inline pii query(int a, int b) {
return query(a, b, 1, 0, n);
}
};
int sequence(int n, vi a) {
vi vals;
for (int x : a) vals.push_back(x);
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for (int i = 0; i < n; i++) {
a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1;
}
int siz = vals.size();
vvi pos(siz + 1);
Seg seg_minus(n + 1), seg_plus(n + 1);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i + 1);
seg_minus.update(i + 1, n + 1, 1);
seg_plus.update(i + 1, n + 1, 1);
}
int ans = 1;
for (int i = 1; i <= siz; i++) {
for (int j : pos[i - 1]) {
seg_plus.update(j, n + 1, -2);
}
for (int j : pos[i]) {
seg_minus.update(j, n + 1, -2);
}
int sz = pos[i].size();
vii minus_before(sz);
vii minus_after(sz);
vii plus_before(sz);
vii plus_after(sz);
for (int k = 0; k < sz; k++) {
int j = pos[i][k];
minus_before[k] = seg_minus.query(0, j);
minus_after[k] = seg_minus.query(j, n + 1);
plus_before[k] = seg_plus.query(0, j);
plus_after[k] = seg_plus.query(j, n + 1);
}
int begin = ans + 1, end = sz + 1, mid;
while (begin < end) {
mid = (begin + end) >> 1;
bool good = false;
for (int ind1 = 0, ind2 = mid - 1; ind2 < pos[i].size(); ind1++, ind2++) {
int l1 = minus_before[ind1].x, r1 = minus_before[ind1].y;
int l2 = minus_after[ind2].x, r2 = minus_after[ind2].y;
if (!(r1 < l2 || r2 < l1)) {
good = true;
break;
}
if (r2 < l1) {
int d = r2 - l1;
if (d + 2 * mid >= 0) {
good = true;
break;
}
}
l1 = plus_before[ind1].x, r1 = plus_before[ind1].y;
l2 = plus_after[ind2].x, r2 = plus_after[ind2].y;
if (!(r1 < l2 || r2 < l1)) {
good = true;
break;
}
if (r1 < l2) {
int d = l2 - r1;
if (d - 2 * mid <= 0) {
good = true;
break;
}
}
}
if (good) begin = mid + 1;
else end = mid;
}
chkmax(ans, begin - 1);
}
return ans;
}
/*
4
3 1 2 2
*/
/*
8
1 1 3 3 2 4 1 1
*/
