#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n, mx = 0, pos = 0;
vector<int> h;
const int N = 1e5 + 5;
int sp[19][N], lg2[N];
int query(int x, int y) {
int j = lg2[y - x + 1];
return max(sp[j][x], sp[j][y - (1 << j) + 1]);
}
void init(int _n, std::vector<int> H) {
h = H;
lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
}
int max_towers(int L, int R, int D) {
vector<int> a;
vector<pair<int, int>> srt;
for (int i = L; i <= R; i++) a.push_back(h[i]);
n = a.size();
for (int i = 0; i < n; i++) sp[0][i] = a[i], srt.push_back({a[i], i});
sort(srt.begin(), srt.end());
lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
for (int i = 1; i < 19; i++) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
set<int> idx;
int ans = 0;
for (int i = 0; i < srt.size(); i++) {
int x = srt[i].second;
bool gone_wrong = 0;
if (!idx.empty() && *idx.begin() < x) {
int k = *--idx.lower_bound(x);
if (query(k, x - 1) < a[x] + D) gone_wrong = 1;
}
if (!gone_wrong && !idx.empty() && *idx.rbegin() > x) {
int k = *idx.lower_bound(x);
if (query(x + 1, k) < a[x] + D) gone_wrong = 1;
}
if (!gone_wrong) {
ans++;
idx.insert(x);
}
}
return ans;
}
