#include <bits/stdc++.h>
using namespace std;
namespace {
int N;
vector<int> H;
using int64 = long long;
const int64 inf = 1e15;
class segment_tree {
int n;
vector<int64> seg;
public:
segment_tree(int n) : n(n), seg(2 * n, -inf) {}
void set(int i, int64 x) {
for (seg[i += n] = x, i >>= 1; i > 0; i >>= 1) {
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int64 query(int l, int r) {
int64 ans = -inf;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = max(ans, seg[l++]);
if (r & 1) ans = max(ans, seg[--r]);
}
return ans;
}
};
} // namespace
void init(int N, vector<int> H) {
::N = N, ::H = H;
}
int max_towers(int L, int R, int D) {
vector<int> h;
for (int i = L; i <= R; ++i) {
h.push_back(H[i]);
}
const int n = R - L + 1;
segment_tree st(n);
for (int i = 0; i < n; ++i) {
st.set(i, h[i]);
}
vector<vector<int>> add(n + 1);
for (int j = 0; j + 2 < n; ++j) {
auto it = ranges::partition_point(views::iota(j + 2, n), [&](int i) {
return st.query(j + 1, i - 1) - D < h[j];
});
add[*it].push_back(j);
}
vector<int64> dp(n, 1);
segment_tree active_dp(n);
for (int i = 0; i < n; ++i) {
for (int &j : add[i]) {
active_dp.set(j, dp[j]);
}
if (i >= 2) {
int j = *ranges::partition_point(views::iota(0, i - 1), [&](int j) {
return st.query(j + 1, i - 1) - D >= h[i];
});
if (j > 0) {
dp[i] = max(dp[i], active_dp.query(0, j - 1) + 1);
}
}
}
return int(*max_element(dp.begin(), dp.end()));
}
