#include "sequence.h"
#include <iostream>
#include <vector>
#include <array>
#define ll int
using namespace std;
vector <ll> V[500000];
struct SegTree{
ll st[4][2000000], lazy[4][2000000];
void push(ll id) {
for (int i=0; i<4; ++i) {
if (!lazy[i][id]) continue;
st[i][id*2] += lazy[i][id];
st[i][id*2+1] += lazy[i][id];
lazy[i][id*2] += lazy[i][id];
lazy[i][id*2+1] += lazy[i][id];
lazy[i][id] = 0;
}
}
void update(ll id, ll l, ll r, ll ql, ll qr, ll z, ll w) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) {
st[z][id] += w;
lazy[z][id] += w;
if (!z) st[1][id] += w, lazy[1][id] += w;
return;
}
push(id);
ll mid = (l+r)/2;
update(id*2, l, mid, ql, qr, z, w);
update(id*2+1, mid+1, r, ql, qr, z, w);
st[z][id] = max(st[z][id*2], st[z][id*2+1]);
st[1][id] = min(st[1][id*2], st[1][id*2+1]);
}
ll query(ll id, ll l, ll r, ll ql, ll qr, ll z) {
if (qr < l || r < ql) return (z != 1 ? -1e9 : 1e9);
else if (ql <= l && r <= qr) return st[z][id];
push(id);
ll mid = (l+r)/2;
return (z != 1 ? max(query(id*2, l, mid, ql, qr, z), query(id*2+1, mid+1, r, ql, qr, z)) : min(query(id*2, l, mid, ql, qr, z), query(id*2+1, mid+1, r, ql, qr, z)));
}
ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll z, ll w) {
if (qr < l || r < ql) return -1e9;
else if (ql <= l && r <= qr) {
ll mid = (l+r)/2;
push(id);
if (st[z][id] >= w) {
if (l == r) return l;
if (st[z][id*2+1] >= w) return queryR(id*2+1, mid+1, r, ql, qr, z, w);
else return queryR(id*2, l, mid, ql, qr, z, w);
}
return -1e9;
}
push(id);
ll mid = (l+r)/2, res = queryR(id*2+1, mid+1, r, ql, qr, z, w);
if (res >= 0) return res;
return queryR(id*2, l, mid, ql, qr, z, w);
}
}ST;
ll a, b, c, d, s, f;
int sequence(int N, std::vector<int> A) {
f = 1;
for (int i=0; i<N; ++i) {
--A[i];
V[A[i]].push_back(i);
ST.update(1, 0, N-1, i, N-1, 0, -1);
ST.update(1, 0, N-1, i, N-1, 2, -1);
ST.update(1, 0, N-1, i, N-1, 3, 1);
}
for (int i=0; i<5e5; ++i) {
for (auto u : V[i]) {
ST.update(1, 0, N-1, u, N-1, 0, 1);
ST.update(1, 0, N-1, u, N-1, 2, 2);
}
ll p = 0, k = 0, s;
for (auto u : V[i]) {
if (p < u) {
auto tmp = ST.query(1, 0, N-1, u, u, 0);
a = tmp - min((p == 0 ? 0 : (ll)1e9), ST.query(1, 0, N-1, max(0, p-1), u, 1)), b = -(tmp-max((p == 0 ? 0 : -(ll)1e9), ST.query(1, 0, N-1, max(0, p-1), u, 0)));
}
else a = b = 0;
a = max(0, a), b = max(0, b);
if (u) s = ST.query(1, 0, N-1, u-1, u-1, 2);
else s = 0;
c = ST.queryR(1, 0, N-1, u, N-1, 2, -a+s);
if (u) s = ST.query(1, 0, N-1, u-1, u-1, 3);
else s = 0;
d = ST.queryR(1, 0, N-1, u, N-1, 3, -b+s);
s = min(c, d);
if (s != -1) {
auto it = lower_bound(V[i].begin(), V[i].end(), s+1);
it = prev(it);
f = max(f, (ll)(it-V[i].begin())-k+1);
}
p = u+1, ++k;
}
for (auto u : V[i]) {
ST.update(1, 0, N-1, u, N-1, 0, 1);
ST.update(1, 0, N-1, u, N-1, 3, -2);
}
}
return f;
}
