#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 le = -1, ri = -1, d = -1;
bitset<100'000> f, r;
vi pref;
int rpos(int i) {return r.size() - i - 1;}
void process(int L, int R, int D) {
f &= 0; r &= 0;
le = L; ri = R; d = D;
for (auto i : idx) {
if (i < le || i > ri) 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));
}
}
bool always = true;
int max_towers(int L, int R, int D) {
// if (d == -1 || always) process(L, R, D);
// return f.count();
return 2;
}
