#include "towers.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, inf = 2e9,LIM = 2001;
vi h;
int up[100001][18];
int rmq(int l,int r) {
if (l > r) return -inf;
int lg = __lg(r-l+1);
return max(up[l][lg],up[r-(1<<lg)+1][lg]);
}
void init(int N, std::vector<int> H) {
h = H;
for (int i = 0;i<N;i++) up[i][0] = H[i];
for (int i=1;i<=17;i++) {
for (int j=0;j+(1<<(i-1))<N;j++) up[j][i] = max(up[j][i-1],up[j+(1<<(i-1))][i-1]);
}
}
int max_towers(int L, int R, int D) {
int ans = 0;
vector<pii> ps;
for (int j=L;j<=R;j++) {
ps.push_back({h[j],j});
}
sort(all(ps));
set<int> taken;
for (auto& [v,p] : ps) {
int fl = 1;
auto it = taken.upper_bound(p);
auto it2 = taken.lower_bound(p);
if (it != taken.end()) {
int mx = rmq(p+1,*it-1);
if (mx < h[p]+D || mx < h[*it]+D) fl = 0;
}
if (it2 != taken.begin()) {
--it2;
int mx = rmq(*it2+1,p-1);
if (mx < h[p]+D || mx < h[*it2]+D) fl = 0;
}
if (fl) {
ans++;
taken.insert(p);
}
}
return ans;
}
