#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<long double>
using namespace std;
const int mxn=1e5+5;
struct node{
int tt,mn,mx;
node*l,*r;
node(int i):tt(1),mn(i),mx(i),l(0),r(0){};
node():tt(0),mn(2e9),mx(-1),l(0),r(0){};
node(node*l,node*r):tt(l->tt+r->tt),mn(min(l->mn,r->mn)),mx(max(l->mx,r->mx)),l(l),r(r){};
};
node*rt[4*mxn];
int t[2*mxn]{0};int n;
int l[mxn],r[mxn],pr[mxn],nx[mxn];
vector<int>h;
vector<int>use;
vector<int>val;
bool ok[mxn]{0},vis[mxn]{0};
node* build(int l,int r){
if(l==r){
if(ok[l])return new node(l);
return new node();
}int m=(l+r)>>1;
return new node(build(l,m),build(m+1,r));
}
node *update(node *t,int l,int r,int idx){
if(l==r){
return new node();
}int m=(l+r)>>1;
if(idx<=m)return new node(update(t->l,l,m,idx),t->r);
return new node(t->l,update(t->r,m+1,r,idx));
}
t3 que(node *t,int l,int r,int tl,int tr){
if(r<tl||l>tr)return {0,2e9,-1};
if(r<=tr&&l>=tl)return make_tuple(t->tt,t->mn,t->mx);
int m=(l+r)>>1;
auto [s1,l1,r1]=que(t->l,l,m,tl,tr);
auto [s2,l2,r2]=que(t->r,m+1,r,tl,tr);
return make_tuple(s1+s2,min(l1,l2),max(r1,r2));
}
int qr(int l,int r,int sz,int rs=0){
for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
if(l&1)rs=max(rs,t[l++]);
if(r&1)rs=max(rs,t[--r]);
}return rs;
}
void init(int N, std::vector<int> H){h=H;
n=N;for(int i=0;i<N;i++)t[i+n]=H[i];
for(int i=n-1;i>=1;i--)t[i]=max(t[2*i],t[2*i+1]);
int pv=-1;
for(int i=0;i<n;i++){
bool ch=0;l[i]=2e9,r[i]=2e9;
pr[i]=i-1;nx[i]=i+1;
if(i==0&&H[i]<H[i+1])ch=1;
else if(i==n-1&&H[i]<H[i-1])ch=1;
else if(H[i]<H[i+1]&&H[i]<H[i-1])ch=1;
if(ch)ok[i]=1,use.pb(i);
if(ch&&pv!=-1){
r[pv]=qr(pv+1,i,n)-H[pv];
l[i]=qr(pv+1,i,n)-H[i];
}if(ch)pv=i;
}priority_queue<pii,vector<pii>,greater<pii>>pq;
for(int i=0;i<use.size();i++){
if(i==0)pr[use[i]]=-1;
else pr[use[i]]=use[i-1];
if(i==(int)use.size()-1)nx[use[i]]=n;
else nx[use[i]]=use[i+1];
}rt[0]=build(0,n-1);val.pb(0);int curr=0,id=0;
for(int i=0;i<n;i++)if(ok[i])pq.push({min(l[i],r[i]),i});
while(!pq.empty()){
auto [d,u]=pq.top();pq.pop();
if(d<min(l[u],r[u])||vis[u])continue;
vis[u]=1;
if(curr!=d+1){
curr=d+1;val.pb(curr);id++;
rt[id]=rt[id-1];
}rt[id]=update(rt[id],0,n-1,u);
if(pr[u]!=-1)nx[pr[u]]=nx[u];
if(nx[u]!=n)pr[nx[u]]=pr[u];
if(pr[u]!=-1&&nx[u]!=n){
r[pr[u]]=qr(pr[u]+1,nx[u],n)-H[pr[u]];
l[nx[u]]=qr(pr[u]+1,nx[u],n)-H[nx[u]];
pq.push({min(r[pr[u]],l[pr[u]]),pr[u]});
pq.push({min(r[nx[u]],l[nx[u]]),nx[u]});
}
else if(pr[u]==-1&&nx[u]!=n){
l[nx[u]]=2e9;pq.push({min(r[nx[u]],l[nx[u]]),nx[u]});
}
else if(pr[u]!=-1&&nx[u]==n){
r[pr[u]]=2e9;pq.push({min(r[pr[u]],l[pr[u]]),pr[u]});
}
}
}
int max_towers(int L, int R, int D) {
if(L==R)return 1;
auto [res,x,y]=que(rt[ub(val,D)-1],0,n-1,L,R);
int cnt=0;
if(res<=1){
int tt = qr(L+1,R,n);
if(tt-h[L]>=D)cnt++;
if(tt-h[R]>=D)cnt++;
if(res==0)return max(cnt,1);
}
if(L==0&&R==n-1)return res;
int chl=0,chr=0;int mn=2e9;
for(int i=L;i<x;i++){
if(h[i]-mn>=D&&h[i]-h[x]>=D)chl=1;
mn=min(mn,h[i]);
}mn=2e9;
for(int i=R;i>y;i--){
if(h[i]-mn>=D&&h[i]-h[y]>=D)chr=1;
mn=min(mn,h[i]);
}return max(res+chl+chr,cnt);
}
