#include "towers.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<int> h;
pair<int, int> st[100005][20];
void init(int N, std::vector<int> H) {
int mx = 0;
for(int i = 0; i < N; ++i){
st[i][0] = {H[i], i};
h.push_back(H[i]);
}
for(int bit = 1; bit <= 19; ++bit){
for(int i = 0; i < N; ++i){
st[i][bit] = max(st[i][bit-1], st[i + (1 << (bit-1))][bit-1]);
}
}
}
int solve(int l, int r, int d, int lim){
if(r < l){
return 0;
}
if(l == r){
if(h[l] <= lim){
return 1;
}else{
return 0;
}
}
int dist = log2(r - l + 1);
int mid = st[l][dist].second;
if(st[r - (1 << dist) + 1][dist].first > st[l][dist].first){
mid = st[r - (1 << dist) + 1][dist].second;
}
return solve(l, mid-1, d, h[mid] - d) + solve(mid+1, r, d, h[mid] - d);
}
int max_towers(int L, int R, int D) {
return solve(L, R, D, 1000000001);
}
