#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n,a[100010],d[100010];
int sp[18][100010],Lg[100010];
int qry(int l,int r){
if (l>r) return -1e9;
int g=Lg[r-l+1];
return max(sp[g][l],sp[g][r-(1<<g)+1]);
}
void init(int N,vector <int> H){
n=N;
for (int i=1; i<=n; i++) a[i]=H[i-1];
for (int i=1; i<=n; i++) sp[0][i]=a[i];
for (int j=1; (1<<j)<=n; j++){
for (int i=1; i+(1<<j)-1<=n; i++) sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
}
Lg[1]=0;
for (int i=2; i<=n; i++) Lg[i]=Lg[i>>1]+1;
int prv[n+1],nxt[n+1];
stack <int> st;
for (int i=1; i<=n; i++){
while (!st.empty()&&a[st.top()]>a[i]) st.pop();
if (st.empty()) prv[i]=0;
else prv[i]=st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i=n; i; i--){
while (!st.empty()&&a[st.top()]>a[i]) st.pop();
if (st.empty()) nxt[i]=0;
else nxt[i]=st.top();
st.push(i);
}
for (int i=1; i<=n; i++){
int lim=1e9;
if (prv[i]) lim=min(lim,qry(prv[i]+1,i-1)-a[i]);
if (nxt[i]) lim=min(lim,qry(i+1,nxt[i]-1)-a[i]);
d[i]=lim;
}
sort(d+1,d+n+1);
}
int max_towers(int L,int R,int D){
L++; R++;
int idx=lower_bound(d+1,d+n+1,D)-d;
return n+1-idx;
}
