#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
vector<int>v,stmax,stmin;
map<int,int>m;
int n;
void build(int i,int l,int r)
{
if(l==r)
{
stmax[i]=v[l];
stmin[i]=v[l];
return;
}
int m=(l+r)/2;
build(2*i,l,m);
build(2*i+1,m+1,r);
stmax[i]=max(stmax[2*i],stmax[2*i+1]);
stmin[i]=min(stmin[2*i],stmin[2*i+1]);
}
int gmax(int i,int l,int r,int tl,int tr)
{
if(l>r||tl>r||l>tr)return 0;
if(tl<=l&&r<=tr)return stmax[i];
int m=(l+r)/2;
return max(gmax(2*i,l,m,tl,tr),gmax(2*i+1,m+1,r,tl,tr));
}
int gmin(int i,int l,int r,int tl,int tr)
{
if(l>r||tl>r||l>tr)return 1e9;
if(tl<=l&&r<=tr)return stmin[i];
int m=(l+r)/2;
return min(gmin(2*i,l,m,tl,tr),gmin(2*i+1,m+1,r,tl,tr));
}
void init(int N, vector<int>H)
{
n=N;
stmax.resize(4*n+1);
stmin.resize(4*n+1);
v.resize(n);
for(int i=0;i<n;i++)
{
v[i]=H[i];
m[v[i]]=i;
}
build(1,0,n-1);
}
int dvq(int l,int r,int k,int d)
{
if(r<l)return 0;
if(r==l)
{
if(v[l]<=k)return 1;
else return 0;
}
int tmin=gmin(1,0,n-1,l,r),tmax=gmax(1,0,n-1,l,r),t=m[tmax];
if(tmin>k)return 0;
else return max(1,dvq(l,t-1,tmax-d,d)+dvq(t+1,r,tmax-d,d));
}
int max_towers(int l,int r,int d)
{
return dvq(l,r,2e9,d);
}
