#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const int maxn = 1e5+10;
const int inf = 1e9+10;
int n, a[maxn];
pair<int,int> trmn[4*maxn], trmx[4*maxn];
void att(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
trmn[no] = mp(val,pos);
trmx[no] = mp(val,pos);
return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)/2;
att(f1,l,mid,pos,val);
att(f2,mid+1,r,pos,val);
trmn[no] = min(trmn[f1],trmn[f2]);
trmx[no] = max(trmx[f1],trmx[f2]);
}
pair<int,int> qrmn(int no, int l, int r, int L, int R) {
if(l > R || r < L) return mp(inf,0);
if(l >= L && r <= R) return trmn[no];
int f1=2*no,f2=2*no+1,mid=(l+r)/2;
return min(qrmn(f1,l,mid,L,R),qrmn(f2,mid+1,r,L,R));
}
pair<int,int> qrmx(int no, int l, int r, int L, int R) {
if(l > R || r < L) return mp(-inf,0);
if(l >= L && r <= R) return trmx[no];
int f1=2*no,f2=2*no+1,mid=(l+r)/2;
return max(qrmx(f1,l,mid,L,R),qrmx(f2,mid+1,r,L,R));
}
void init(int N, vector<int> H) {
n = N;
for(int i = 0; i < n; i++) {
a[i] = H[i];
att(1,0,n-1,i,a[i]);
}
}
int sol(int l, int r, int d) {
int i = qrmx(1,0,n-1,l,r).sc;
int ans = 0;
if(i != l && qrmn(1,0,n-1,l,i-1).fr <= a[i]-d) ans+= max(1,sol(l,i-1,d));
if(i != r && qrmn(1,0,n-1,i+1,r).fr <= a[i]-d) ans+= max(1,sol(i+1,r,d));
// cout << l << " " << r << " " << d << " " << ans << endl;
return max(1,ans);
}
int max_towers(int L, int R, int D) {
return sol(L,R,D);
}
