#include "towers.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
class segtree {
public:
std::vector<ll> seg;
ll n;
segtree() : n(0) {}
segtree(ll n) : n(n), seg(4 * n) {}
void set(ll v, ll l, ll r, ll idx, ll del) {
if (idx < l or idx > r) {
return;
}
if (l == r) {
seg[v] = del;
return;
}
ll m = l + (r - l) / 2;
set(2 * v, l, m, idx, del);
set(2 * v + 1, m + 1, r, idx, del);
seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}
void set(ll idx, ll del) {
set(1, 0, n - 1, idx, del);
}
ll q(ll v, ll l, ll r, ll ql, ll qr) {
if (qr < l or ql > r) {
return 0;
}
if (ql <= l and r <= qr) {
return seg[v];
}
ll m = l + (r - l) / 2;
return max(q(2 * v, l, m, ql, qr), q(2 * v + 1, m + 1, r, ql, qr));
}
ll q(ll ql, ll qr) {
if (ql > qr)
return 0;
return q(1, 0, n - 1, ql, qr);
}
};
int n;
vector<pair<ll, ll>> h;
segtree st;
segtree counted;
void init(int N, vector<int> H) {
n = N;
set<ll> s;
for (int i = 0; i < H.size(); i++) {
h.push_back({H[i], i});
}
st = segtree(n);
counted = segtree(n);
sort(h.begin(), h.end());
};
int max_towers(int l, int r, int d) {
for (int i = 0; i < n; i++) {
if (h[i].second >= l and h[i].second <= r)
st.set(h[i].second, h[i].first);
}
ll cc = 1;
int ans = 1;
for (int i = 0; i < n; i++) {
if (!(h[i].second >= l and h[i].second <= r))
continue;
if (cc--) {
counted.set(h[i].second, 1);
} else {
ll left = l - 1;
ll right = r + 1;
ll check = 0;
ll lll = l, rr = h[i].second - 1;
while (lll <= rr and check == 0) {
ll mid = lll + (rr - lll) / 2;
if (st.q(mid, h[i].second - 1) >= h[i].first + d) {
left = mid;
lll = mid + 1;
} else {
rr = mid - 1;
}
}
lll = h[i].second + 1, rr = r;
while (lll <= rr and check == 0) {
ll mid = lll + (rr - lll) / 2;
if (st.q(lll, mid) >= h[i].first + d) {
right = mid;
rr = mid - 1;
} else {
lll = mid + 1;
}
}
if (check == 0 and counted.q(left + 1, right - 1) == 0) {
counted.set(h[i].second, 1);
ans++;
}
}
}
return ans;
};
