#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e5; const ll K = 500; const ll INF = 1e18;
map<ll,array<ll,3>> mdn[Nm/K]; //D -> {start #, end #, # of terms}
//start down: go DUDUD...
map<ll,array<ll,3>> mup[Nm/K];
ll H0[Nm];
void pdn(ll T, vector<ll> v0, ll Dmin, bool isDn) {
if (Dmin>=INF/2) {
Dmin =INF/2;
}
//cout << "T,isDn="<<T<<","<<isDn<<"\n";
//cout << "Dmin="<<Dmin<<"\n";
ll Dc = INF;
ll x2p = -INF; ll xp = INF; ll xc = INF; bool cdown = 1;
//isDn -> first move is down
if (!isDn) {
x2p = INF; xp = -INF; xc = -INF; cdown = 0;
}
ll nfirst = -1;
ll len = 0;
for (ll x0: v0) {
if (cdown) {
if (x0<xc && (xp-x0)>=Dmin) {
xc = x0;
if ((xp-xc)>=Dmin) {
//cout << "into Dc: xp,x2p="<<xp<<","<<x2p<<"\n";
Dc = min(Dc,xp-x2p);
if (len==1) {
nfirst = xp;
}
len++;
x2p = xp; xp = xc; cdown = 0; xc = -INF;
//cout << "flipping; new (x2p,xp,xc)="<<x2p<<","<<xp<<","<<xc<<"\n";
}
} else if (x0>xp) {
xp = x0; xc = INF;
//cout << "1push down prev to "<<x0<<"\n";
}
} else {
//cout << "x0,xp="<<x0<<","<<xp<<"\n";
if (x0>xc && (x0-xp)>=Dmin) {
xc = x0;
if ((xc-xp)>=Dmin) {
Dc = min(Dc,x2p-xp);
if (len==1) {
nfirst = xp;
}
len++;
x2p = xp; xp = xc; cdown = 1; xc = INF;
//cout << "flipping; new (x2p,xp,xc)="<<x2p<<","<<xp<<","<<xc<<"\n";
}
} else if (x0<xp) {
xp = x0; xc = -INF;
//cout << "2push up prev to "<<x0<<"\n";
}
}
}
Dc = min(Dc,abs(x2p-xp));
assert(Dc>=Dmin);
if (Dmin>=(INF/2)) {
assert(len<=1);
}
if (len==0) {
if (isDn) {
//cout << "creating mdn[INF]: "<<xc<<","<<xc<<","<<1<<"\n";
mdn[T][INF]={xc,xc,1};
} else {
//cout << "creating mup[INF]: "<<xc<<","<<xc<<","<<1<<"\n";
mup[T][INF]={xc,xc,1};
}
} else {
if (len==1) {
nfirst = xp;
}
if (isDn) {
//cout << "creating mdn["<<Dc<<"]: "<<nfirst<<","<<xp<<","<<len<<"\n";
mdn[T][Dc]={nfirst,xp,len};
} else {
//cout << "creating mdn["<<Dc<<"]: "<<nfirst<<","<<xp<<","<<len<<"\n";
mup[T][Dc]={nfirst,xp,len};
}
if (len>1) {
pdn(T,v0,Dc+1,isDn);
}
}
}
void init(int N, vector<int> H) {
for (ll i=0;i<N;i++) {
H0[i]=H[i];
}
for (ll T=0;T<(Nm/K);T++) {
vector<ll> cnum;
for (ll i=0;i<K;i++) {
cnum.push_back(H0[i+T*K]);
}
pdn(T,cnum,0,1);
pdn(T,cnum,0,0);
}
}
struct seg {
bool ifdn; //is first down?
ll len; //number of terms
ll x0,x1; //first and last terms
seg(ll xc, bool bdn) {
len = 1;
ifdn = bdn;
x0 = xc; x1 = xc;
}
seg(ll _x0, ll _x1, ll _len, bool _ifdn) {
x0 = _x0; x1 = _x1; len = _len; ifdn = _ifdn;
}
};
struct endp {
ll vup,vdn,lup,ldn;
//vup: (min) value of the previous term (upon going up)
//vdn: (max) value of the previous term (upon going down)
//lup/ldn: number of DOWNS so far
endp() {
vup = -INF; lup = 0;
vdn = INF; ldn = 0;
}
void fz(seg s0, ll D) {
ll vup1 = vup; ll vdn1 = vdn; ll lup1 = lup; ll ldn1 = ldn;
if (s0.ifdn) { //first step is going down aka DUDU...
//vup: ...DUD so far
pii ptest = {(lup+(s0.len+1)/2-1),s0.x1};
if ((s0.len%2)==0) {
//ends in U -> going down -> vdn
if (ptest.first>ldn1) {
ldn1 = ptest.first; vdn1 = ptest.second;
} else if (ptest.first==ldn1) {
vdn1 = max(vdn1,ptest.second);
}
} else {
//ends in D -> going up -> vup
if (ptest.first>lup1) {
lup1 = ptest.first; vup1 = ptest.second;
} else if (ptest.first==lup1) {
vup1 = min(vup1,ptest.second);
}
}
//vdn: ...UDU so far
if ((vdn-s0.x0)>=D) {
ptest = {(ldn+(s0.len+1)/2),s0.x1};
} else {
ptest = {(ldn-1+(s0.len+1)/2),s0.x1};
}
//copy and paste rest of code
if ((s0.len%2)==0) {
//ends in U -> going down -> vdn
if (ptest.first>ldn1) {
ldn1 = ptest.first; vdn1 = ptest.second;
} else if (ptest.first==ldn1) {
vdn1 = max(vdn1,ptest.second);
}
} else {
//ends in D -> going up -> vup
if (ptest.first>lup1) {
lup1 = ptest.first; vup1 = ptest.second;
} else if (ptest.first==lup1) {
vup1 = min(vup1,ptest.second);
}
}
} else { //first step is going up aka UDUD...
//vup: ...DUD so far
pii ptest;
if ((s0.x0-vup)>=D) {
ptest = {lup+(s0.len)/2,s0.x1};
} else {
ptest = {lup+(s0.len)/2-1,s0.x1};
}
//copy and paste rest of code
if ((s0.len%2)==1) {
//ends in U -> going down -> vdn
if (ptest.first>ldn1) {
ldn1 = ptest.first; vdn1 = ptest.second;
} else if (ptest.first==ldn1) {
vdn1 = max(vdn1,ptest.second);
}
} else {
//ends in D -> going up -> vup
if (ptest.first>lup1) {
lup1 = ptest.first; vup1 = ptest.second;
} else if (ptest.first==lup1) {
vup1 = min(vup1,ptest.second);
}
}
//vdn: ...UDU so far
ptest = {ldn+s0.len/2,s0.x1};
//copy and paste rest of code
if ((s0.len%2)==1) {
//ends in U -> going down -> vdn
if (ptest.first>ldn1) {
ldn1 = ptest.first; vdn1 = ptest.second;
} else if (ptest.first==ldn1) {
vdn1 = max(vdn1,ptest.second);
}
} else {
//ends in D -> going up -> vup
if (ptest.first>lup1) {
lup1 = ptest.first; vup1 = ptest.second;
} else if (ptest.first==lup1) {
vup1 = min(vup1,ptest.second);
}
}
}
vup = vup1; vdn = vdn1; lup = lup1; ldn = ldn1;
}
ll getans() {
return max(lup,ldn);
}
void print() {
cout << "vup,lup="<<vup<<","<<lup<<"; vdn,ldn="<<vdn<<","<<ldn<<"\n";
}
};
endp maxp(endp s0, endp s1) {
endp s2;
if (s0.ldn!=s1.ldn) {
if (s0.ldn>s1.ldn) {
s2.ldn=s0.ldn;
s2.vdn=s0.vdn;
} else {
s2.ldn=s1.ldn;
s2.vdn=s1.vdn;
}
} else {
s2.ldn=s0.ldn;
s2.vdn=max(s0.vdn,s1.vdn);
}
if (s0.lup!=s1.lup) {
if (s0.lup>s1.lup) {
s2.lup=s0.lup;
s2.vup=s0.vup;
} else {
s2.lup=s1.lup;
s2.vup=s1.vup;
}
} else {
s2.lup=s0.lup;
s2.vup=min(s0.vup,s1.vup);
}
return s2;
}
int max_towers(int L, int R, int D) {
ll kl = L/K; ll kr = R/K;
endp s0;
if (kl==kr) {
for (ll i=L;i<=R;i++) {
endp s1 = s0; endp s2 = s0;
s1.fz(seg(H0[i],0),D);
s2.fz(seg(H0[i],1),D);
s0 = maxp(s1,s2);
// cout << "after a new number: \n";
// s0.print();
}
} else {
for (ll i=L;i<K*(1+kl);i++) {
endp s1 = s0; endp s2 = s0;
s1.fz(seg(H0[i],0),D);
s2.fz(seg(H0[i],1),D);
s0 = maxp(s1,s2);
}
for (ll i=(1+kl);i<kr;i++) {
endp s1 = s0; endp s2 = s0;
auto A0 = (*mdn[i].lower_bound(D)).second;
s1.fz(seg(A0[0],A0[1],A0[2],1),D);
auto A1 = (*mup[i].lower_bound(D)).second;
s2.fz(seg(A1[0],A1[1],A1[2],0),D);
s0 = maxp(s1,s2);
}
for (ll i=(kr*K);i<=R;i++) {
endp s1 = s0; endp s2 = s0;
s1.fz(seg(H0[i],0),D);
s2.fz(seg(H0[i],1),D);
s0 = maxp(s1,s2);
}
}
return s0.getans();
}
