#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], dn[100100], t2[400400];
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 = 0, int r = N-1) {
if(r < nl || !t[u].s) return -1;
if(l == r) return l;
int re = find_first(t[u].l, nl, l, mid);
if(re != -1) return re;
return find_first(t[u].r, nl, mid+1, r);
}
int find_last(int u, int nr, int l = 0, int r = N-1) {
if(nr < l || !t[u].s) return -1;
if(l == r) return l;
int re = find_last(t[u].r, nr, mid+1, r);
if(re != -1) return re;
return find_last(t[u].l, nr, l, mid);
}
int build(int node = 1, int l = 0, int r = N-1) {
if(l == r) return t2[node] = H[l];
return t2[node] = min(build(node*2, l, mid), build(node*2+1, mid+1, r));
}
int find_min(int nl, int nr, int node = 1, int l = 0, int r = N-1) {
if(r < nl || nr < l) return 1e9;
if(nl <= l && r <= nr) return t2[node];
return min(find_min(nl, nr, node*2, l, mid), find_min(nl, nr, node*2+1, mid+1, 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]});
if(H[A[i]] < H[A[i+1]]) dn[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);
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});
}
build();
}
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;
int LL = find_first(rt[u], L), RR = find_last(rt[u], R);
ans = (ans + dn[LL]) / 2;
if(L < LL && find_min(L, LL-1)+D <= H[LL]) ans++;
if(RR < R && find_min(RR+1, R)+D <= H[RR]) ans++;
return max(1, ans);
}
