#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){};
};
struct node2{
int mn,mx,amx;
node2 operator+(node2 b){
return {min(mn,b.mn),max(mx,b.mx),max({amx,b.amx,b.mx-mn})};
}
};
struct node3{
int mn,mx,amx;
node3 operator+(node3 b){
return {min(mn,b.mn),max(mx,b.mx),max({amx,b.amx,mx-b.mn})};
}
};
const int inf=1e9;
node*rt[4*mxn];
node2 sg2[4*mxn];
node3 sg3[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};
void build2(int i,int l,int r){
if(l==r)return void(sg2[i]={h[l],h[l],0});
int m=(l+r)>>1;build2(2*i,l,m);build2(2*i+1,m+1,r);
sg2[i]=sg2[2*i]+sg2[2*i+1];
}
node2 qr2(int i,int l,int r,int tl,int tr){
if(r<tl||l>tr)return node2{inf,-1,0};
if(r<=tr&&l>=tl)return sg2[i];
int m=(l+r)>>1;
return qr2(2*i,l,m,tl,tr)+qr2(2*i+1,m+1,r,tl,tr);
}
void build3(int i,int l,int r){
if(l==r)return void(sg3[i]={h[l],h[l],0});
int m=(l+r)>>1;build3(2*i,l,m);build3(2*i+1,m+1,r);
sg3[i]=sg3[2*i]+sg3[2*i+1];
}
node3 qr3(int i,int l,int r,int tl,int tr){
if(r<tl||l>tr)return node3{-1,inf,0};
if(r<=tr&&l>=tl)return sg3[i];
int m=(l+r)>>1;
return qr3(2*i,l,m,tl,tr)+qr3(2*i+1,m+1,r,tl,tr);
}
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(i>0&&i<n-1&&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]});
}
}build2(1,0,n-1);build3(1,0,n-1);
}
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);
if(L==0&&R==n-1)return res;
if(res==0){
int l=L,r=R+1;
while(l<r){
int md=(l+r)>>1;
if(qr2(1,0,n-1,L,md).amx>=D)r=md;
else l=md+1;
}
if(l!=R+1){
res++;
if(qr3(1,0,n-1,l,R).amx>=D)res++;
}
return max(1,res);
}res+=(qr2(1,0,n-1,L,x-1).amx>=D)+(qr3(1,0,n-1,y+1,R).amx>=D);
return res;
}
