#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
using vi = vector<int>;
using vvi = vector<vi>;
/*
greedy left to right (sorted order) bitset idea
(2 incompatible towers that make valid subsets of the same size theres no reason not to use the smaller one)
*/
struct SegTree {
#define midpoint (l+(r-l)/2)
#define is_leaf (l+1==r)
#define left_child 2*i+1, l, midpoint
#define right_child 2*i+2, midpoint, r
#define root 0, 0, n
int n; vi st, arr;
SegTree() {}
SegTree(int n, vi arr) : n(n), arr(arr), st(4*n, INT_MIN) {build(root);}
int build(int i, int l, int r) {
if (is_leaf) return st[i] = arr[l];
return st[i] = max(build(left_child), build(right_child));
}
int query(int ql, int qr) {return query(root, ql, qr);}
int query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return INT_MIN;
if (ql <= l && r <= qr) return st[i];
return max(query(left_child, ql, qr), query(right_child, ql, qr));
}
};
int n; vi h, idx;
SegTree st;
void init(int N, vi H) {
n = N; h = H;
idx.assign(n, 0); iota(all(idx), 0);
sort(all(idx), [&](int i, int j) {return h[i] < h[j];});
st = SegTree(n, H);
}
int max_towers(int L, int R, int d) {
bitset<200'000> f, r;
auto rpos = [&](int i) {return r.size() - i - 1;};
for (auto i : idx) {
if (i < L || i > R) continue;
int prev = rpos(r._Find_next(rpos(i)));
int nxt = f._Find_next(i);
bool good = true;
if (prev > -1 && st.query(prev, i+1) - h[i] < d) good = false;
if (nxt < f.size() && st.query(i, nxt+1) - h[i] < d) good = false;
if (good) f.set(i), r.set(rpos(i));
}
return f.count();
}
