#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 10;
const int LOG = 17;
int h[N];
int tab[LOG][N];
int n;
void init(int _n, vector<int> H) {
n = _n;
for(int i = 0 ; i < n; i ++ ){
h[i] = H[i];
tab[0][i] = h[i];
}
for(int ln = 1; ln < LOG; ln ++ ){
for(int i = 0 ; i + (1 << ln) - 1 < n; i ++ ){
tab[ln][i] = min(tab[ln-1][i], tab[ln-1][i + (1 << (ln - 1))]);
}
}
}
int D = -1;
int jump[LOG][N];
void compute_diff(int dd){
if(D != dd){
D = dd;
for(int i = 0 ; i <= n; i ++ ){
jump[0][i] = n;
}
int lf, rf;
for(int c = 1; c + 1 < n; c ++ ){
lf = c;
rf = c;
for(int ln = LOG - 1; ln >= 0 ; ln -- ){
if(lf - (1 << ln) >= 0 && tab[ln][lf - (1 << ln)] > h[c] - dd){
lf -= (1 << ln);
}
if(rf + (1 << ln) < n && tab[ln][rf + 1] > h[c] - dd){
rf += (1 << ln);
}
}
lf -- ;
rf ++ ;
if(lf < 0) continue;
jump[0][lf] = min(jump[0][lf], rf);
}
for(int i = n - 1; i >= 0; i -- ){
jump[0][i]=min(jump[0][i],jump[0][i+1]);
}
for(int l = 1; l < LOG; l ++ ){
for(int i = 0 ; i <= n; i ++ ){
jump[l][i]=jump[l-1][jump[l-1][i]];
}
}
}
}
int max_towers(int L, int R, int delta) {
compute_diff(delta);
int res = 1;
for(int ln = LOG - 1; ln >= 0 ; ln -- ){
if(jump[ln][L] <= R){
L=jump[ln][L];
res += (1 << ln);
}
}
return res;
}
