// In the name of Allah
#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define Mp make_pair
#define pb push_back
#define endl '\n'
#define sep ' '
const int maxn = 1e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;
int n;
ll Ax[maxn], A[maxn]; set<int> st;
int arr[maxn], rmq[maxn][maxlg];
bool cmp(int i, int j) {
return (A[i] < A[j]);
}
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < n; i++) Ax[i] = H[i];
}
int get_max(int l, int r) {
int j = __lg(r - l);
return max(rmq[l][j], rmq[r - (1 << j)][j]);
}
bool check(int i, int j, int D) {
if (j - i + 1 <= 2) return 0;
int mx = get_max(i + 1, j);
return (mx >= max(A[i], A[j]) + D);
}
bool ok(int i, int D) {
auto it = st.lower_bound(i);
if (it != st.end()) {
if (!check(i, *it, D)) return 0;
}
if (it != st.begin()) {
it--;
if (!check(*it, i, D)) return 0;
}
return 1;
}
int max_towers(int L, int R, int D) {
for (int j = L; j <= R; j++) A[j - L] = Ax[j];
n = R - L + 1;
for (int i = n - 1; i >= 0; i--) {
rmq[i][0] = A[i];
for (int j = 1; j < maxlg; j++) {
if (i + (1 << j) - 1 >= n) break;
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
st.clear();
iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
for (int j = 0; j < n; j++) {
int i = arr[j];
if (ok(i, D)) st.insert(i);
}
return len(st);
}
