#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
class segTree {
int n;
vector<int> seg;
void upd(int node, int start, int end, int idx, int v) {
if (start == end) {
seg[node] = v;
}
else {
int mid = (start + end) / 2;
if (idx <= mid) upd(node*2, start, mid, idx, v);
else upd(node*2+1, mid+1, end, idx, v);
seg[node] = max(seg[node*2], seg[node*2+1]);
}
}
int query(int node, int start, int end, int l, int r) {
if (start > r || end < l) return 0;
else if (start >= l && end <= r) return seg[node];
else {
int mid = (start + end) / 2;
return max(query(node*2, start, mid, l, r), query(node*2+1, mid+1, end, l, r));
}
}
public:
void initt(int nn) {
n = nn;
seg.assign(4*(n+1), 0);
}
void upd(int idx, int v) {
upd(1, 0, n-1, idx, v);
}
int query(int l, int r) {
if (l > r) return 0;
return query(1, 0, n-1, l, r);
}
};
segTree seg1, seg2;
void init(int N, std::vector<int> H) {
n = N;
h = H;
seg1.initt(n);
seg2.initt(n);
for (int i = 0; i < n; i++) {
seg2.upd(i, h[i]);
}
}
int max_towers(int L, int R, int D) {
vector<int> dp(n, 1);
int ans = 1;
int d = D;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = L; i <= R; i++) {
int lo = L+1, hi = i-1;
int fin = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int mx = seg2.query(mid, i-1);
if (h[i] + d <= mx) {
fin = mid;
lo = mid+1;
}
else {
hi = mid-1;
}
}
if (fin != -1) {
dp[i] = max(dp[i], seg1.query(L, fin-1) + 1);
}
while (!pq.empty() && pq.top().first + d <= h[i]) {
int idx = pq.top().second;
pq.pop();
seg1.upd(idx, dp[idx]);
}
pq.push({h[i], i});
ans = max(ans, dp[i]);
}
return ans;
}
