#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=18,kaf=(1<<lg),inf=1e9+5;
int all[maxn];
struct segmentmin{
pair<long long ,long long>seg[(1<<(lg+1))];
segmentmin(){
for(int i=2*kaf-1;i>=0;i--){
if(i>=kaf){
seg[i].second=i-kaf;
}else{
seg[i].second=seg[(i<<1)].second;
}
}
}
void ins(int i,int w){
i+=kaf;
seg[i].first=w;
i>>=1;
while(i>0){
seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
pair<long long ,long long> pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return make_pair(inf,inf);
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}segmn;
struct segmentmax{
pair<long long ,long long>seg[(1<<(lg+1))];
segmentmax(){
for(int i=2*kaf-1;i>=0;i--){
if(i>=kaf){
seg[i].second=i-kaf;
}else{
seg[i].second=seg[(i<<1)].second;
}
}
}
void ins(int i,int w){
i+=kaf;
seg[i].first=w;
i>>=1;
while(i>0){
seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
pair<long long ,long long> pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return make_pair(0,0);
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}segmx;
int n;
void init(int N, std::vector<int> H) {
n=N;
for(int i=0;i<n;i++){
all[i]=H[i];
segmx.ins(i,H[i]);
segmn.ins(i,H[i]);
}
}
int solve(int l,int r,int d){
if(l==r){
return 1;
}
int ind=segmx.pors(1,0,kaf-1,l,r).second;
int cl=0,cr=0,ret=0;
if(segmn.pors(1,0,kaf-1,l,ind-1).first<=all[ind]-d){
cl=solve(l,ind-1,d);
}
if(segmn.pors(1,0,kaf-1,ind+1,r).first<=all[ind]-d){
cr=solve(ind+1,r,d);
}
ret=cl+cr;
//cout<<"wtF: "<<l<<" "<<r<<" "<<d<<" "<<cl<<" "<<cr<<endl;
ret=max(ret,1);
return ret;
}
int max_towers(int L, int R, int D) {
return solve(L,R,D);
}
