#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<int>a;
struct Node{
int mx;
int mxind;
int mn;
int mnind;
Node():mx(0),mn(0),mxind(0),mnind(0){}
void bld(int vl, int ind){
mx=mn=vl;
mxind=mnind=ind;
}
void join(const Node& lft, const Node& rgh){
if(lft.mx>=rgh.mx){
mx=lft.mx;
mxind=lft.mxind;
}
else{
mx=rgh.mx;
mxind=rgh.mxind;
}
if(lft.mn<=rgh.mn){
mn=lft.mn;
mnind=lft.mnind;
}
else{
mn=rgh.mn;
mnind=rgh.mnind;
}
}
};
Node t[4*N];
void build(int v, int tl, int tr){
if(tl==tr){
t[v].bld(a[tl], tl);
}
else{
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v].join(t[2*v],t[2*v+1]);
}
}
pair<int,int> get_max(int v, int tl, int tr, int l, int r){
if(l>r)return {0,0};
if(tl==l&&tr==r)return {t[v].mx, t[v].mxind};
else{
int tm=(tl+tr)/2;
return max(get_max(2*v,tl,tm,l,min(tm,r)),
get_max(2*v+1,tm+1,tr,max(tm+1,l),r));
}
}
pair<int,int> get_min(int v, int tl, int tr, int l, int r){
if(l>r)return {MOD,MOD};
if(tl==l&&tr==r)return {t[v].mn,t[v].mnind};
else{
int tm=(tl+tr)/2;
return min(get_min(2*v,tl,tm,l,min(tm,r)),
get_min(2*v+1,tm+1,tr,max(tm+1,l),r));
}
}
int recurs(int l, int r, int vl, int d){
if(l>r)return 0;
int mx=get_max(1,0,n-1,l,r).ss,
mn=get_min(1,0,n-1,l,r).ss;
if(a[mn]>vl-d)return 0;
int lft=recurs(l,mx-1,a[mx],d);
int rgh=recurs(mx+1,r,a[mx],d);
// cout<<l<<" "<<r<<" "<<vl<<" "<<d<<": ";
// cout<<a[mn]<<", "<<a[mx]<<", ";
if(lft==0&&rgh==0){
// cout<<1<<endl;
return 1;
}
// cout<<lft+rgh<<endl;
return lft+rgh;
}
void init(int NN, vector<int> H) {
n=NN;
a=H;
build(1,0,n-1);
}
int max_towers(int L, int R, int D) {
return recurs(L,R,2e9+7,D);
}
