#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll val[POT*15][5],lw[POT*15][5],pw[POT*15][5];//0 sum,1 min,2 min(na ujemnych)
ll ak[5];
ll h[100007][17];
ll p1[100007],p2[100007];
ll pop[100007],nxt[100007];
vector<pair<ll,ll>>root[3];// <moment,nowy root>
void st(ll cop,ll v,ll vl,ll idx,ll l,ll r,ll gdz){
lw[v][idx]=lw[cop][idx];
pw[v][idx]=pw[cop][idx];
if((l+r)/2>=gdz){
lw[v][idx]=ak[idx];
}
else pw[v][idx]=ak[idx];
ak[idx]++;
if(l==r){
val[v][idx]=vl;
}
else{
if((l+r)/2>=gdz)st(lw[cop][idx],lw[v][idx],vl,idx,l,(l+r)/2,gdz);
else st(pw[cop][idx],pw[v][idx],vl,idx,(l+r)/2+1,r,gdz);
if(idx)
val[v][idx]=min(val[lw[v][idx]][idx],val[pw[v][idx]][idx]);
else val[v][idx]=val[lw[v][idx]][idx]+val[pw[v][idx]][idx];
}
}
ll get(ll v,ll l,ll r,ll pocz,ll kon,ll idx){
if(pocz > r || kon < l)return idx*INFL;
if(pocz<=l && kon>=r)return val[v][idx];
if(idx)return min(get(lw[v][idx],l,(l+r)/2,pocz,kon,idx),get(pw[v][idx],(l+r)/2+1,r,pocz,kon,idx));
else return get(lw[v][idx],l,(l+r)/2,pocz,kon,idx)+get(pw[v][idx],(l+r)/2+1,r,pocz,kon,idx);
}
ll mx(ll pocz,ll kon){
if(pocz>kon)return 0;
ll lg=log2(kon-pocz+1);
return max(h[pocz][lg],h[kon-(1<<lg)+1][lg]);
}
void init(int n,vector<int>H){
root[0].pb({INFL,0});
root[1].pb({INFL,0});
root[2].pb({INFL,0});
ak[0]=20;ak[1]=20;ak[2]=20;ak[3]=20;ak[4]=20;
for(ll i=0;i<n;i++)h[i][0]=H[i];
for(ll i=0;i<20;i++){
for(ll idx=0;i<5;i++){
lw[i][idx]=i+1;
pw[i][idx]=i+1;
}
}
for(ll i=0;i<15*POT;i++){
for(ll j=1;j<5;j++)val[i][j]=INFL;
}
stack<pair<ll,ll>>stt;
stt.push({-1,-1});
for(ll i=0;i<n;i++){
while(h[i][0]<=stt.top().ff)stt.pop();
pop[i]=stt.top().ss;
stt.push({h[i][0],i});
}
while(stt.size()>1)stt.pop();
stt.top().ss=n;
for(ll i=n-1;i>=0;i--){
while(h[i][0]<=stt.top().ff)stt.pop();
nxt[i]=stt.top().ss;
stt.push({h[i][0],i});
}
for(ll j=1;j<17;j++){
for(ll i=0;i+(1<<j)<=n;i++)h[i][j]=max(h[i][j-1],h[i+(1<<(j-1))][j-1]);
}
vector<pair<ll,ll>>zd;//<czas,kto>
for(ll i=0;i<n;i++){
p1[i]=mx(pop[i]+1,i-1)-h[i][0];
p2[i]=mx(i+1,nxt[i]-1)-h[i][0];
zd.pb({min(p1[i],p2[i]),-i-INFL});
if(p1[i]>p2[i]){
zd.pb({p1[i],-i-1});
}
else zd.pb({p2[i],i});
}
sort(zd.begin(),zd.end());
reverse(zd.begin(),zd.end());
for(auto op :zd){
if(op.ss<=-INFL){
ll i=-op.ss-INFL;
root[0].pb({op.ff,ak[0]});
st(root[0][root[0].size()-2].ss,ak[0]++,1,0,1,POT/2,i+1);
st(root[0][root[0].size()-2].ss,ak[3]++,i+1,3,1,POT/2,i+1);
st(root[0][root[0].size()-2].ss,ak[4]++,-i-1,4,1,POT/2,i+1);
if(p1[i]>p2[i]){
root[1].pb({op.ff,ak[1]});
st(root[1][root[1].size()-2].ss,ak[1]++,INFL,1,1,POT/2,i+1);
}
else{
root[2].pb({op.ff,ak[2]});
st(root[2][root[2].size()-2].ss,ak[2]++,INFL,2,1,POT/2,i+1);
}
}
else if(op.ss<0){
ll i=-op.ss-1;
root[1].pb({op.ff,ak[1]});
st(root[1][root[1].size()-2].ss,ak[1]++,-nxt[i]-1,1,1,POT/2,i+1);
}
else{
ll i=op.ss;
root[2].pb({op.ff,ak[2]});
st(root[2][root[2].size()-2].ss,ak[2]++,pop[i]+1,2,1,POT/2,i+1);
}
}
for(ll i=0;i<3;i++)reverse(root[i].begin(),root[i].end());
}
ll max_towers(int l,int r,int d){
l++;
r++;
ll r0=(*lower_bound(root[0].begin(),root[0].end(),pair<ll,ll>{d,-INFL})).ss;
ll r1=(*lower_bound(root[1].begin(),root[1].end(),pair<ll,ll>{d,-INFL})).ss;
ll r2=(*lower_bound(root[2].begin(),root[2].end(),pair<ll,ll>{d,-INFL})).ss;
ll ans=get(r0,1,POT/2,l,r,0);
ll lew=get(r0,1,POT/2,l,r,3)-1;
ll prw=-get(r0,1,POT/2,l,r,4)+1;
if(ans==0){
lew=r;
prw=l;
}
if(-get(r1,1,POT/2,prw,r,1)>r)ans++;
if(get(r2,1,POT/2,l,lew,2)<l)ans++;
return max(ans,1LL);
}
