#include "towers.h"
#include "bits/stdc++.h";
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct pii{int a, b;};
const int MN = 1e5 + 10;
int h[MN], n;
void init(int N, std::vector<int> H) {
n = N;
forR(i, N) h[i] = H[i];
}
int l[MN], r[MN], cmax[MN];
struct event{int ti, i, ty;}; // 0: L, 1: i
int bit[MN];
void upd(int i, int to) {
bit[i] = max(bit[i], to);
}
int qu(int i) {
int ret = bit[i];
for(; i >= 0; --i) ret = max(ret, bit[i]);
return ret;
}
int max_towers(int L, int R, int D) {
REP(i, L, R+1) {
int j;
for(j = i; j >= L && h[j] < h[i] + D; --j);
l[i] = j;
for(j = i; j <= R && h[j] < h[i] + D; ++j);
r[i] = j;
}
vector<event> evs;
REP(i, L, R+1) {
evs.push_back({l[i], i, 0});
evs.push_back({i, i, 1});
}
sort(all(evs), [](event& a, event& b){return a.ti < b.ti || a.ti == b.ti && a.ty == 0 && b.ty != 0;});
for(auto [ti, i, ty] : evs) {
if(ty == 0) {
cmax[i] = qu(i) + 1;
} else {
upd(r[i] + 1, cmax[i]);
}
}
return qu(MN - 1);
}
