#include "sequence.h"
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;
const int MXN = 5e5;
vector<int> ct[MXN + 1];
int pref[4 * MXN + 10], pref1[4 * MXN + 10], suff[4 * MXN + 10], suff1[4 * MXN + 10], sm1[4 *MXN + 10], sm2[4 *MXN + 10], arr[MXN + 1];
void merge(int c, int a, int b) {
pref[c] = max(pref[a], sm1[a] + pref[b]);
pref1[c] = min(pref1[a], sm2[a] + pref1[b]);
suff[c] = max(suff[b], sm1[b] + suff[a]);
suff1[c] = min(suff1[a], sm2[b] + suff1[a]);
sm1[c] = sm1[a] + sm1[b];
sm2[c] = sm2[a] + sm2[b];
}
void build(int lf, int rg, int nd) {
if(lf == rg) {
if(arr[lf] == 0) {
pref[nd] = suff[nd] = 1;
pref1[nd] = suff1[nd] = -1;
sm1[nd] = 1;
sm2[nd] = -1;
}
else {
sm1[nd] = sm2[nd] = pref[nd] = suff[nd] = 1;
pref1[nd] = suff1[nd] = 0;
}
} else {
int mid = (lf + rg) / 2;
build(lf, mid, 2*nd+1);
build(mid+1, rg, 2*nd+2);
merge(nd, 2*nd+1, 2*nd+2);
}
}
void upd(int lf, int rg, int nd, int pos, int v) {
if(lf == rg) {
int v1, v2;
if(v == 0) {
v1 = 1;
v2 = -1;
} else {
v1 = v2 = v;
}
sm1[nd] = v1;
sm2[nd] = v2;
pref[nd] = suff[nd] = max(0, v1);
pref1[nd] = suff1[nd] = min(0, v2);
} else {
int mid = (lf + rg) / 2;
if(pos <= mid) upd(lf, mid, 2*nd+1, pos, v);
else upd(mid+1, rg, 2*nd+2, pos, v);
merge(nd, 2*nd+1, 2*nd+2);
}
}
pair<int, pair<int, int> > qry(int lf, int rg, int nd, int clf, int crg, int v) {
if(clf > rg || lf > crg) return make_pair(0, make_pair(0, 0));
if(clf <= lf && rg <= crg) {
if(v) return make_pair(sm1[nd], make_pair(pref[nd], suff[nd]));
else return make_pair(sm2[nd], make_pair(pref1[nd], suff1[nd]));
} else {
int mid = (lf + rg) / 2;
pair<int, pair<int, int> > a, b;
a = qry(lf, mid, 2*nd+1, clf, crg, v);
b = qry(mid+1, rg, 2*nd+2, clf, crg, v);
if(v) return make_pair(a.fi + b.fi, make_pair(max(a.se.fi, a.fi + b.se.fi), max(b.se.se, a.se.se + b.fi)));
else return make_pair(a.fi + b.fi, make_pair(min(a.se.fi, a.fi + b.se.fi), min(b.se.se, a.se.se + b.fi)));
}
}
int N1;
int fen[500001];
int sm[500001];
void add(int a, int b) {
while(a <= N1) {
fen[a] += b;
a += a&(-a);
}
}
void ad(int a, int b) {
while(a <= N1) {
sm[a] += b;
a += a&(-a);
}
}
int qy(int a) {
int as = 0;
while(a > 0) {
as += fen[a];
a -= a&(-a);
}
return as;
}
int qqy(int a) {
int as = 0;
while(a > 0) {
as += sm[a];
a -= a&(-a);
}
return as;
}
bool cek(int a, int b) {
int d;
d = qqy(b + 1) - qqy(a);
// if(a == 0 && b == 8) cout<<"D : "<<a<<" "<<b<<" "<<d.fi<<" "<<d.se.fi<<" "<<d.se.se<<endl;
int lr = qy(b + 1) - qy(a);
// if(a == 0 && b == 8) cout<<lr<<endl;
if(lr >= abs(d)) return 1;
else {
if(d < 0) {
d += qry(0, N1 - 1, 0, 0, a-1, 1).se.se + qry(0, N1-1, 0, b+1, N1-1, 1).se.fi;
if(d > 0) d = 0;
} else {
d += qry(0, N1-1, 0, 0, a-1, 0).se.se + qry(0, N1-1, 0, b+1, N1-1, 0).se.fi;
if(d < 0) d = 0;
}
if(lr >= abs(d)) return 1;
else return 0;
}
return 0;
}
int sequence(int N, vector<int> A) {
N1 = N;
map<int, int> mp;
for(int i=0;i<N;i++) mp[A[i]] = 1;
int cnt = 0;
for(auto p : mp) mp[p.fi] = cnt++;
for(int i=0;i<=N;i++) sm[i] = fen[i] = 0;
for(int i=0;i<N;i++) {
arr[i] = mp[A[i]];
if(arr[i] == 0) add(i + 1, 1);
else ad(i + 1, 1);
ct[arr[i]].push_back(i);
}
build(0, N-1, 0);
int ans = 0;
for(int i=0;i<cnt;i++) {
int r = 0;
for(int k=0;k<ct[i].size();k++) {
// cout<<i<<" "<<k<<" "<<r<<endl;
// if(i == 1 && r < ct[i].size()) cout<<r<<" "<<cek(ct[i][k], ct[i][r])<<endl;
while(r < ct[i].size() && cek(ct[i][k], ct[i][r])) {
r++;
// cout<<"r : "<<r<<endl;
}
// cout<<"i : "<<i<<" "<<k<<" "<<r<<endl;
ans = max(ans, r - k);
}
for(int d=0;d<ct[i].size();d++) {
upd(0, N-1, 0, ct[i][d], -1);
ad(ct[i][d] + 1, -1);
add(ct[i][d] + 1, -1);
}
for(int d=0;d<ct[i+1].size();d++) {
upd(0, N-1, 0, ct[i+1][d], 0);
ad(ct[i+1][d] + 1, -1);
add(ct[i+1][d] + 1, 1);
}
// cout<<qry(0, N-1, 0, 0, N-1, 0).fi<<endl;
}
return ans;
}
