#include "towers.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll INF=1LL<<60;
struct SegTree {
vector<int> tree;
int size;
SegTree(int sz) {
tree.resize(sz*2,0);
size=sz;
}
void resize(int sz) {
tree.resize(sz*2,0);
size=sz;
}
void set(int p,int v) {
p+=size;
tree[p]=v;
p/=2;
while(p>=1) {
tree[p]=max(tree[p*2],tree[p*2+1]);
p/=2;
}
}
int prod(int l,int r) {
int ret=0;
l+=size;
r+=size;
while(l<r) {
if(l&1) {
ret=max(ret,tree[l]);
l++;
}
if(r&1) {
r--;
ret=max(ret,tree[r]);
}
l/=2;
r/=2;
}
return ret;
}
};
bool flg=false;
vector<int> h;
int n;
SegTree seg(0);
vector<int> lf;
vector<int> hr;
vector<int> ri;
vector<vector<int>> dbl;
void init(int N, std::vector<int> H) {
h=H;
n=N;
seg.resize(N);
rep(i,N) {
seg.set(i,H[i]);
}
}
void init_by_d(int d) {
lf.resize(n+1,n);
hr.resize(n+1,n);
ri.resize(n+1,n);
dbl.resize(20,vector<int>(n+1,0));
rep(i,n) {
int ok,ng;
ok=-1;
ng=i;
while(abs(ok-ng)>1) {
int mid=(ok+ng)/2;
if(seg.prod(mid,i)>=h[i]+d)ok=mid;
else ng=mid;
}
int l=ok;
ok=n;
ng=i;
while(abs(ok-ng)>1) {
int mid=(ok+ng)/2;
if(seg.prod(i,mid+1)>=h[i]+d)ok=mid;
else ng=mid;
}
if(l!=-1) {
lf[l]=min(lf[l],ok);
hr[l]=min(hr[l],i);
}
ri[i]=ok;
}
rrep(i,n) {
lf[i]=min(lf[i],lf[i+1]);
ri[i]=min(ri[i],ri[i+1]);
hr[i]=min(hr[i],hr[i+1]);
}
dbl[0]=lf;
rng(i,1,20) {
rep(j,n+1) {
dbl[i][j]=dbl[i-1][dbl[i-1][j]];
}
}
}
int max_towers(int L, int R, int D) {
if(!flg) {
flg=true;
init_by_d(D);
}
if(R<ri[L])return 1;
int pos=ri[L];
int ans=1;
rrep(i,20) {
if(dbl[i][pos]<=R) {
ans+=1<<i;
pos=dbl[i][pos];
}
}
if(hr[pos]<=R)ans++;
return ans;
}
