#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 524288; const ll E = 19;
const ll INF = 1e18;
ll stmax[2*Nm];
ll stmin[2*Nm];
ll stsum[2*Nm];
ll v2(ll x) {
if (x==0) {
return 100;
}
return __builtin_ctz(x);
}
ll l2(ll x) {
return (31-__builtin_clz(x));
}
void wipe() {
for (ll i=0;i<(2*Nm);i++) {
stmax[i]=0;
stmin[i]=0;
stsum[i]=0;
}
}
void upd(ll x, ll d) {
//updates value at x to d
ll p = Nm+x;
stsum[p]=d;
stmax[p]=d;
stmin[p]=d;
p=p/2;
while (p>0) {
stsum[p]=stsum[2*p]+stsum[2*p+1];
stmax[p]=max(stmax[2*p],stsum[2*p]+stmax[2*p+1]);
stmin[p]=min(stmin[2*p],stsum[2*p]+stmin[2*p+1]);
p=p/2;
}
}
ll sum(ll x) {
if (x<0) {
return 0;
}
ll lx = v2(x+1);
return (stsum[(x>>lx)+(1LL<<(E-lx))]+sum(x-(1LL<<lx)));
}
ll minr(ll a, ll lL) { //first index, log2 of length
return (sum(a-1)+stmin[(a>>lL)+(1LL<<(E-lL))]);
}
ll maxr(ll a, ll lL) { //see above
return (sum(a-1)+stmax[(a>>lL)+(1LL<<(E-lL))]);
}
ll qmin(ll a, ll b) {
if (a>b) {
return INF;
}
ll la = v2(a); ll lb = v2(b+1);
if (la<=lb) {
return min(minr(a,la),qmin(a+(1LL<<la),b));
} else {
return min(qmin(a,b-(1LL<<lb)),minr(((b>>lb)<<lb),lb));
}
}
ll qmax(ll a, ll b) {
if (a>b) {
return -INF;
}
ll la = v2(a); ll lb = v2(b+1);
if (la<=lb) {
return max(maxr(a,la),qmax(a+(1LL<<la),b));
} else {
return max(qmax(a,b-(1LL<<lb)),maxr(((b>>lb)<<lb),lb));
}
}
ll bsmin(ll a, ll b, ll mv) { //find largest index value in this range with array value <=mv
if (a==b) {
return a;
}
ll lg = min(v2(b+1),l2(b-a));
if (minr(((b>>lg)<<lg),lg)<=mv) {
return bsmin(b-(1LL<<lg)+1,b,mv);
} else {
return bsmin(a,b-(1LL<<lg),mv);
}
}
int sequence(int N, vector<int> A) {
ll ans = 1;
wipe();
for (ll i=0;i<N;i++) {
upd(i,-1);
}
map<ll,vector<ll>> m0; //map: value -> index positions
for (ll i=0;i<N;i++) {
m0[A[i]].push_back(i);
}
for (auto PTR: m0) {
//cout << "processing number "<<PTR.first<<"\n";
vector<ll> v0 = PTR.second;
map<ll,ll> indv;
ll K = v0.size();
for (ll k=0;k<K;k++) {
indv[v0[k]]=k;
}
ll fval[K];
ll prev = -1;
for (ll k=0;k<K;k++) {
ll MV = qmax(prev,v0[k]);
ll xmin=v0[k]; ll xmax=N-1;
/*while (xmin != xmax) {
ll xq = (xmin+xmax+1)/2;
if (MV>=qmin(xq,N-1)) {
xmin=xq;
} else {
xmax=xq-1;
}
}*/
xmin = bsmin(xmin,Nm-1,MV); //find largest index with value <=MV
//cout << "k="<<k<<", bsmin="<<xmin<<"\n";
auto PT2 = indv.upper_bound(xmin);
PT2--;
fval[k]=((*PT2).second)+1-k;
//cout << "k="<<k<<", MV="<<MV<<"\n";
prev=v0[k];
}
for (ll k=0;k<K;k++) {
upd(v0[k],1);
}
prev = -1;
for (ll k=0;k<K;k++) {
ll MV = qmin(prev,v0[k]);
ll xmin=v0[k]; ll xmax=N-1;
while (xmin != xmax) {
ll xq = (xmin+xmax+1)/2;
if (MV<=qmax(xq,N-1)) {
xmin=xq;
} else {
xmax=xq-1;
}
}
//cout << "k="<<k<<", xmin="<<xmin<<"\n";
//xmin = bsmax(xmin,Nm-1,MV); //find largest index with value >=MV
auto PT2 = indv.upper_bound(xmin);
PT2--;
ans=max(ans,min(((*PT2).second)+1-k,fval[k]));
prev=v0[k];
}
}
return ans;
}
