#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 18;
int n;
vector<int> h;
vector<int> spa[LOG];
int get_max(int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
return max(spa[lg][l], spa[lg][r - (1 << lg) + 1]);
}
void init(int N_, vector<int> H_) {
n = N_, h = H_;
spa[0] = h;
for (int j = 1; (1 << j) <= n && j < LOG; ++j) {
spa[j].resize(n - (1 << j) + 1);
for (int i = 0; i + (1 << j) <= n; ++i) {
spa[j][i] = max(spa[j - 1][i], spa[j - 1][i + (1 << (j - 1))]);
}
}
}
int max_towers(int l, int r, int d) {
vector<int> ord;
for (int i = l; i <= r; ++i) {
ord.push_back(i);
}
sort(ord.begin(), ord.end(), [&](int i, int j) {
return h[i] < h[j];
});
set<int> se;
for (int i : ord) {
auto it = se.lower_bound(i);
bool ok = true;
if (it != se.end()) {
int nxt = *it;
if (nxt == i + 1 || get_max(i + 1, nxt - 1) < h[i] + d) {
ok = false;
}
}
if (it != se.begin()) {
int pre = *prev(it);
if (pre == i - 1 || get_max(pre + 1, i - 1) < h[i] + d) {
ok = false;
}
}
if (ok) {
se.insert(i);
}
}
return (int) se.size();
}
