#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mid ((l+r) >> 1)
struct Node {
int l, r, s;
} t[10010010];
int tc;
int N, rt[100100];
vector<int> H, A, DL;
int update(int u, int id, int val, int l = 0, int r = N-1) {
if(id < l || r < id) return u;
int x = ++tc;
t[x] = t[u], t[x].s += val;
if(l == r) return x;
t[x].l = update(t[x].l, id, val, l, mid);
t[x].r = update(t[x].r, id, val, mid+1, r);
return x;
}
int find(int u, int nl, int nr, int l = 0, int r = N-1) {
if(!u || nr < l || r < nl) return 0;
if(nl <= l && r <= nr) return t[u].s;
return find(t[u].l, nl, nr, l, mid) + find(t[u].r, nl, nr, mid+1, r);
}
int find_first(int u, int nl) {
int l = nl, r = N-1;
while(l <= r) {
if(find(u, nl, mid)) r = mid-1;
else l = mid+1;
}
return l;
}
int find_last(int u, int nr) {
int l = 0, r = nr;
while(l <= r) {
if(find(u, mid, nr)) l = mid+1;
else r = mid-1;
}
return r;
}
void init(int N, vector<int> H) {
::N = N, ::H = H;
A.push_back(0), A.push_back(1);
for(int i=2;i<N;i++) {
if((H[A.rbegin()[1]] < H[A.back()]) == (H[A.back()] < H[i])) A.pop_back();
A.push_back(i);
}
priority_queue<array<int, 3>> pq;
for(int i=0;i+1<A.size();i++) {
pq.push({-abs(H[A[i]]-H[A[i+1]]), A[i], A[i+1]});
}
set<int> s;
for(int i=0;i<A.size();i++) s.insert(A[i]), rt[0] = update(rt[0], A[i], 1);
int prv = 0, dc = 0;
while(!pq.empty()) {
auto [c, a, b] = pq.top(); pq.pop();
if(!s.count(a) || !s.count(b)) continue;
int L = dc, R = dc;
if(prv != c) R = ++dc, prv = c, DL.push_back(-c);
rt[R] = update(rt[L], a, -1);
rt[R] = update(rt[R], b, -1);
// cout << L << " " << R << " " << find(rt[R], 0, N-1) << "\n";
s.erase(a);
auto it = s.erase(s.find(b));
if(it != s.begin() && it != s.end()) pq.push({-abs(H[*it] - H[*prev(it)]), *prev(it), *it});
}
}
int max_towers(int L, int R, int D) {
if(L+1 >= R) return 1;
int u = lower_bound(DL.begin(), DL.end(), D) - DL.begin();
if(u == DL.size()) return 1;
int ans = find(rt[u], L, R);
if(ans == 0) return 1;
ans = (ans + 1) / 2;
int LL = find_first(rt[u], L), RR = find_last(rt[u], R);
// cout << u << " " << find(rt[u], 0, N-1) << " " << ans << "]\n";
// cout << LL << " " << RR << "\n";
auto it = lower_bound(A.begin(), A.end(), L);
if(it != A.end() && *it < LL && H[*it]+D <= H[LL]) ans++;
else if(++it != A.end() && *it < LL && H[*it]+D <= H[LL]) ans++;
else if(L < LL & H[L]+D <= H[LL]) ans++;
it = upper_bound(A.begin(), A.end(), R);
if(prev(it) != A.begin()){
it--;
if(RR < *it && H[*it]+D <= H[RR]) ans++;
else if(it != A.begin() && RR < *prev(it) && H[*prev(it)]+D <= H[RR]) ans++;
else if(RR < R && H[R]+D <= H[RR]) ans++;
} else if(RR < R && H[R]+D <= H[RR]) ans++;
return ans;
}
