#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) {
vector<int> mono;
REP(i, L, R+1) {
int ind = upper_bound(all(mono), h[i] + D, [](int a, int b){return a > h[b];}) - mono.begin() - 1;
l[i] = ind == -1 ? L-1 : mono[ind];
while(!mono.empty() && h[mono.back()] <= h[i]) mono.pop_back();
mono.push_back(i);
}
mono.clear();
for(int i = R; i >= L; --i) {
int ind = upper_bound(all(mono), h[i] + D, [](int a, int b){return a > h[b];}) - mono.begin() - 1;
r[i] = ind == -1 ? R + 1 : mono[ind];
while(!mono.empty() && h[mono.back()] <= h[i]) mono.pop_back();
mono.push_back(i);
}
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);
}
