#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
const int INF = 1e9;
struct SegNode {
int mx = -INF;
int mn = INF;
SegNode merge(SegNode other) {
return {max(mx, other.mx), min(mn, other.mn)};
}
};
struct SegTree {
vec<SegNode> data;
vec<int> lazy;
vec<pair<SegNode, int>> suff_cache;
vec<pair<SegNode, int>> pref_cache;
int n;
int upd_ind = 1;
SegTree(vec<int> init_data) {
n = 1;
while(n<init_data.size()) n*=2;
data = vec<SegNode>(n*2);
lazy = vec(n*2, 0);
suff_cache = vec<pair<SegNode, int>>(n);
pref_cache = vec<pair<SegNode, int>>(n);
for(int i = 0; i<init_data.size(); i++) {
data[i+n] = {init_data[i], init_data[i]};
}
for(int i = n-1; i > 0; i--) {
data[i] = data[i*2].merge(data[i*2+1]);
}
}
SegNode query_suffix(int l) {
if(suff_cache[l].second != upd_ind) suff_cache[l] = {query(l, n), upd_ind};
return suff_cache[l].first;
}
SegNode query_prefix(int r) {
if(pref_cache[r-1].second != upd_ind) pref_cache[r-1] = {query(0, r), upd_ind};
return pref_cache[r-1].first;
}
void push(int i) {
data[i].mx += lazy[i];
data[i].mn += lazy[i];
if(i*2 > n*2) {
lazy[i] = 0;
return;
}
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
SegNode query(int l, int r, int i = 1, int ll = 0, int rr = -1) {
if(rr == -1) rr = n;
push(i);
if(ll >= r || rr <= l) return {};
if(ll >= l && rr <= r) return data[i];
int mm = (ll+rr)/2;
return query(l, r, i*2, ll, mm).merge(query(l, r, i*2+1, mm, rr));
}
void upd(int l, int r, int val, int i = 1, int ll = 0, int rr = -1) {
upd_ind++;
if(rr == -1) rr = n;
push(i);
if(ll >= r || rr <= l) return;
if(ll >= l && rr <= r) {
lazy[i] += val;
push(i);
return;
}
int mm = (ll+rr)/2;
upd(l, r, val, i*2, ll, mm);
upd(l, r, val, i*2+1, mm, rr);
data[i] = data[i*2].merge(data[i*2+1]);
}
};
int sequence(int n, std::vector<int> a) {
int ans = 0;
vec<vec<int>> val_inds(n+1);
for(int i = 0; i<n; i++) {
val_inds[a[i]].push_back(i);
}
vec<int> st1_init(n+1);
vec<int> st2_init(n+1);
iota(st1_init.begin(), st1_init.end(), 0);
iota(st2_init.begin(), st2_init.end(), 0);
SegTree st1(st1_init);
SegTree st2(st2_init);
for(int i = 1; i<=n; i++) {
for(int j = 0; j<val_inds[i-1].size(); j++) {
st1.upd(val_inds[i-1][j]+1, n+1, -2);
}
for(int j = 0; j<val_inds[i].size(); j++) {
st2.upd(val_inds[i][j]+1, n+1, -2);
}
int k_l = 1;
int k_r = val_inds[i].size()+1;
while(k_l < k_r) {
int k = (k_l+k_r)/2;
bool found = false;
for(int j = k-1; j<val_inds[i].size(); j++) {
int l = val_inds[i][j-(k-1)];
int r = val_inds[i][j]+1;
if(st1.query_suffix(r).mx - st1.query_prefix(l+1).mn >= 0 &&
st2.query_suffix(r).mn - st2.query_prefix(l+1).mx <= 0) {
ans = max(ans, k);
found = true;
break;
}
}
if(found) k_l = k+1;
else k_r = k;
}
}
return ans;
}
