#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define mp make_pair
using ii = pair<int, int>;
int N;
vector<int> H;
void init(int N, vector<int> H) {
::N = N;
::H = H;
}
int max_towers(int L, int R, int D) {
vector<int> V(H.begin() + L, H.begin() + R + 1), cl(V.size(), -1), cr(V.size(), V.size());
vector<ii> vec;
for (int i = 0; i < (int)V.size(); i++) {
{
int lo = 0, hi = (int)vec.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (vec[mid].first <= V[i] - D) {
cl[i] = vec[mid].second;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
while (!vec.empty() && vec.back().first >= V[i]) {
vec.pop_back();
}
vec.eb(V[i], i);
}
vec.clear();
for (int i = (int)V.size() - 1; i >= 0; i--) {
{
int lo = 0, hi = (int)vec.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (vec[mid].first <= V[i] - D) {
cr[i] = vec[mid].second;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
while (!vec.empty() && vec.back().first >= V[i]) {
vec.pop_back();
}
vec.eb(V[i], i);
}
vector<ii> segs;
for (int i = 0; i < (int)V.size(); i++) {
if (cl[i] != -1) {
segs.eb(cr[i], cl[i]);
}
}
sort(segs.begin(), segs.end());
int ans = 0, max_r = -1;
for (auto [r, l] : segs) {
if (l >= max_r) {
ans++;
max_r = r;
}
}
return ans + 1;
}
