#pragma GCC optimize("Ofast")
#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define ref(x) (*(x))
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else
#define debug(...)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
ostream& operator << (ostream& out, vector<T> v) {
for(auto& i : v) {
out << i << " ";
}
return out;
}
struct node {
int lb, rb, mn, mx, lazy, lc, rc;
};
ostream& operator << (ostream& out, node v) {
cout << v.lb << " " << v.rb << " " << v.mn << " " << v.mx << " " << v.lazy << " " << v.lc << " " << v.rc << " ";
return out;
}
struct segtree {
vector<node> nodes;
segtree(int l, int r) {
nodes.reserve((r - l + 1) * 2);
build(l, r);
}
void build(int l, int r) {
int idx = sz(nodes);
nodes.push_back({l, r, l, r, 0, -1, -1});
if(l == r) {
return;
}
int mid = (l + r) / 2;
nodes[idx].lc = sz(nodes);
build(l, mid);
nodes[idx].rc = sz(nodes);
build(mid + 1, r);
}
void sadd(int l, int r, int v, int idx = 0) {
int lb = nodes[idx].lb, rb = nodes[idx].rb;
if(r < lb || l > rb) {
return;
}
if(l <= lb && r >= rb) {
nodes[idx].lazy += v;
return;
}
int lc = nodes[idx].lc, rc = nodes[idx].rc;
sadd(l, r, v, lc);
sadd(l, r, v, rc);
nodes[idx].mx = max(nodes[lc].mx + nodes[lc].lazy, nodes[rc].mx + nodes[rc].lazy);
nodes[idx].mn = min(nodes[lc].mn + nodes[lc].lazy, nodes[rc].mn + nodes[rc].lazy);
}
int qrymx(int l, int r, int idx = 0) {
int lb = nodes[idx].lb, rb = nodes[idx].rb;
if(r < lb || l > rb) {
return INT_MIN;
}
if(l <= lb && r >= rb) {
return nodes[idx].mx + nodes[idx].lazy;
}
int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0;
ret = max(qrymx(l, r, lc), qrymx(l, r, rc));
return ret + nodes[idx].lazy;
}
int qrymn(int l, int r, int idx = 0) {
int lb = nodes[idx].lb, rb = nodes[idx].rb;
if(r < lb || l > rb) {
return INT_MAX;
}
if(l <= lb && r >= rb) {
return nodes[idx].mn + nodes[idx].lazy;
}
int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0;
ret = min(qrymn(l, r, lc), qrymn(l, r, rc));
return ret + nodes[idx].lazy;
}
};
int sequence(int N, std::vector<int> A) {
debug(N); debug(A);
vector<int> sids(N);
for(int i = 0; i < N; i++) {
sids[i] = i;
}
sort(sids.begin(), sids.end(), [&](int a, int b) {
if(A[a] != A[b]) {
return A[a] < A[b];
} else {
return a < b;
}
});
int ptr = 0, mx = 1;
segtree eqpos(0, N), eqneg(0, N);
while(ptr < N) {
for(int i = ptr; i < N && A[sids[i]] == A[sids[ptr]]; i++) {
eqneg.sadd(sids[i] + 1, N, -2);
}
int nptr = ptr;
while(nptr < N && A[sids[nptr]] == A[sids[ptr]]) {
if(nptr + mx >= N) {
return mx;
}
int l = sids[nptr], r = sids[nptr + mx];
if(A[l] != A[r]) {
nptr++;
continue;
}
if(eqpos.qrymx(r + 1, N) - eqpos.qrymn(0, l) >= 0 && eqneg.qrymn(r + 1, N) - eqneg.qrymx(0, l) <= 0) {
mx++;
} else {
nptr++;
}
}
for(; ptr < nptr; ptr++) {
eqpos.sadd(sids[ptr] + 1, N, -2);
}
}
return mx;
}
