#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
int t, n, h[N], pr[N], par[lg][N], par2[lg][N];
void init(int _N, vector<int> _H) {
n = _N;
for(int i=1; i<=n; i++) {
h[i] = _H[i - 1];
}
for(int i=n; i>=1; i--) {
par[0][i] = i;
par2[0][i] = i;
for(int j=1; j<lg; j++) {
int x = par[j-1][i], y = par[j-1][min(n, i+(1<<(j-1)))];
par[j][i] = (h[x] > h[y] ? x : y);
x = par2[j-1][i], y = par2[j-1][min(n, i+(1<<(j-1)))];
par2[j][i] = (h[x] < h[y] ? x : y);
}
}
}
int getmx(int l, int r) {
int res = l;
for(int i=lg-1; i>=0; i--) {
if(l + (1<<i) <= r + 1) {
res = (h[res] > h[par[i][l]] ? res : par[i][l]);
l += (1<<i);
}
}
return res;
}
int getmn(int l, int r) {
int res = l;
for(int i=lg-1; i>=0; i--) {
if(l + (1<<i) <= r + 1) {
res = (h[res] < h[par2[i][l]] ? res : par2[i][l]);
l += (1<<i);
}
}
return res;
}
int divide(int l, int r, int mx, int d) {
if(l > r) return 0;
int mini = getmn(l, r);
int maxi = getmx(l, r);
int ldp = divide(l, maxi - 1, h[maxi] - d, d), rdp = divide(maxi + 1, r, h[maxi] - d, d);
return max(ldp + rdp, (int)(h[mini] <= mx));
}
int max_towers(int l, int r, int d) {
l++, r++;
if(r == l) return 1;
return divide(l, r, 1e9, d);
}
