#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,lg=17;
const ll inf=2e9+50;
int n,a[N];
int Maks[N][lg+1],LOG[N+50];
int MAKS(int l,int r){if(l>r)return 0;int i=LOG[r-l+1];return max(Maks[l][i],Maks[r-(1<<i)+1][i]);}
int Lm[N],Rm[N];
vector<pair<ll,ll>>nesto;
int root[N];
struct PersistentSegTree{
int nc,lc[N*(lg+5)],rc[N*(lg+5)],sum[N*(lg+5)];
void Update(int &c,int c1,int ss,int se,int qind,int x){
c=++nc;lc[c]=lc[c1],rc[c]=rc[c1],sum[c]=sum[c1];
if(ss==se){sum[c]=x;return;}
int mid=ss+se>>1;
if(qind<=mid) Update(lc[c],lc[c1],ss,mid,qind,x);
else Update(rc[c],rc[c1],mid+1,se,qind,x);
sum[c]=sum[lc[c]]+sum[rc[c]];
}
int Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qe<ss||se<qs)return 0;
if(qs<=ss&&se<=qe)return sum[c];
int mid=ss+se>>1;return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}
}PST;
struct Node{ll maks,mn,ind,val1,val2;};
Node Merge(Node a,Node b){
Node c;
c.maks=max(a.maks,b.maks);
c.mn=min(a.mn,b.mn);
if(a.mn<=b.mn) c.ind=a.ind;
else c.ind=b.ind;
c.val1=max({a.val1,b.val1,b.maks-a.mn});
c.val2=max({a.val2,b.val2,a.maks-b.mn});
return c;
}
struct SegTree1{
int root,nc,lc[2*N],rc[2*N];Node node[2*N];
void Build(int &c,int ss,int se){
c=++nc;
if(ss==se){node[c]={a[ss],a[ss],ss,0,0};return;}
int mid=ss+se>>1;
Build(lc[c],ss,mid),Build(rc[c],mid+1,se);
node[c]=Merge(node[lc[c]],node[rc[c]]);
}
Node Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qe<ss||se<qs)return {0,inf,0,0};
if(qs<=ss&&se<=qe)return node[c];
int mid=ss+se>>1;return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
}ST1;
void init(int N, std::vector<int> H){
n=N;
for(int i=1;i<=n;i++) a[i]=H[i-1];
for(int i=1,e=1,ct=-1;i<=N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
for(int i=1;i<=n;i++) Maks[i][0]=a[i];
for(int j=0;j<lg;j++) for(int i=1;i<=n;i++) if(i+(1<<j)<=n) Maks[i][j+1]=max(Maks[i][j],Maks[i+(1<<j)][j]);
vector<int>mono;
for(int i=1;i<=n;i++){
Lm[i]=0,Rm[i]=n+1;
while(!mono.empty()&&a[mono.back()]>a[i]){
Rm[mono.back()]=i;
mono.pop_back();
}
if(!mono.empty()) Lm[i]=mono.back();
mono.pb(i);
}
for(int i=1;i<=n;i++){
ll x=inf,y=inf;
if(Lm[i]>0) x=MAKS(Lm[i]+1,i-1);
if(Rm[i]<=n) y=MAKS(i+1,Rm[i]-1);
nesto.pb({min(x,y)-a[i],i});
}
sort(nesto.begin(),nesto.end());
reverse(nesto.begin(),nesto.end());
for(int i=0;i<nesto.size();i++) PST.Update(root[i+1],root[i],1,n,nesto[i].se,1);
ST1.Build(ST1.root,1,n);
}
int max_towers(int L, int R, int D){
L++,R++;
int l=0,r=n-1,ind,rt;
while(l<=r){
int mid=l+r>>1;
if(nesto[mid].fi>=D){ind=mid;l=mid+1;}
else r=mid-1;
}
rt=root[ind+1];
int res=PST.Get(rt,1,n,L,R);
if(res==0) res=1;
l=L,r=R;
int levo=ST1.Get(ST1.root,1,n,L,R).ind;
while(l<=r){
int mid=l+r>>1;
int x=PST.Get(rt,1,n,L,mid);
if(x>0){levo=mid;r=mid-1;}
else l=mid+1;
}
l=L,r=levo-1;
int L1=L-1;
while(l<=r){
int mid=l+r>>1;
ll x=MAKS(mid,levo-1);
if(x-D>=a[levo]){L1=mid;l=mid+1;}
else r=mid-1;
}
if(ST1.Get(ST1.root,1,n,L,L1).val1>=D) res++;
l=L,r=R;
int desno=ST1.Get(ST1.root,1,n,L,R).ind;
while(l<=r){
int mid=l+r>>1;
int x=PST.Get(rt,1,n,mid,R);
if(x>0){desno=mid;l=mid+1;}
else r=mid-1;
}
l=desno+1,r=R;
int R1=R+1;
while(l<=r){
int mid=l+r>>1;
ll x=MAKS(desno+1,mid);
if(x-D>=a[desno]){R1=mid;r=mid-1;}
else l=mid+1;
}
if(ST1.Get(ST1.root,1,n,R1,R).val2>=D) res++;
return res;
}
