#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
int a[mxn], n, T[mxn][20];
int query(int l, int r) {
int k = __lg(r - l + 1);
return max( T[l][k], T[r-(1<<k)+1][k] );
}
void init(int _n, vector<int> H) {
n = _n;
for(int i=0; i<n; i++) {
a[i] = H[i];
T[i][0] = a[i];
}
for(int j=1; j<20; j++)
for(int i=0; i+(1<<j)-1<n; i++)
T[i][j] = max( T[i][j-1], T[i+(1<<(j-1))][j-1] );
}
int max_towers(int L, int R, int D) {
int ans = 1;
set<int> st;
vector<pair<int, int> > ord;
for(int i=L; i<=R; i++) ord.push_back({ a[i], i });
sort(ord.begin(), ord.end());
for(auto [h, id] : ord) {
if(st.empty()) {
st.insert(id);
continue;
}
int ok = 1;
auto it = st.lower_bound(id);
if(it != st.end()) {
if(*it == id + 1) {
ok = 0;
} else {
int mx = query(id+1, *it-1);
if(max(a[id], a[*it]) > mx - D) ok = 0;
}
}
if(it != st.begin()) {
--it;
if(*it == id - 1) {
ok = 0;
} else {
int mx = query(*it+1, id-1);
if(max(a[id], a[*it]) > mx - D) ok = 0;
}
}
if(ok) {
st.insert(id);
ans++;
}
}
return ans;
}
