#include <bits/stdc++.h>
// #include "towers.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define sz(x) (signed)(x.size())
#define all(x) x.begin(),x.end()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define endl '\n'
#define F "file"
#define fio freopen(F".inp","r",stdin);freopen(F".out","w",stdout);
using namespace std;
const int N=1e5+3;
int n,a[N],st[2*N],l1[N],r1[N];
stack<int> sta;
void build(int id,int l,int r) {
if (l==r) return void(st[id]=a[l]);
int mid=l+r>>1;
build(id+1,l,mid);
build(id+2*(mid-l+1),mid+1,r);
st[id]=max(st[id+1],st[id+2*(mid-l+1)]);
}
int query(int id,int l,int r,int u,int v) {
if (l>v || r<u) return -1;
if (l>=u && r<=v) return st[id];
int mid=l+r>>1;
return max(query(id+1,l,mid,u,v),query(id+2*(mid-l+1),mid+1,r,u,v));
}
void init(int N,vector<int> H) {
n=N;
For(i,0,n-1) a[i+1]=H[i];
fill(l1,l1+1+n,-1);
fill(r1,r1+1+n,n+1);
For(i,1,n) {
while (sz(sta) && a[sta.top()]>a[i]) {
r1[sta.top()]=i;
sta.pop();
}
sta.push(i);
}
while(sz(sta)) sta.pop();
ForD(i,n,1) {
while (sz(sta) && a[sta.top()]>a[i]) {
l1[sta.top()]=i;
sta.pop();
}
sta.push(i);
}
build(1,1,n);
}
int max_towers(int l,int r,int d) {
l++,r++;
int ans=0;
For(i,l,r) {
bool check=1;
if (l1[i]>=l) check&=(query(1,1,n,l1[i],i)-d>=a[i]);
if (r1[i]<=r) check&=(query(1,1,n,i,r1[i])-d>=a[i]);
ans+=check;
}
return ans;
}
