#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));
}
};
struct Fenw {
int n; vector<int> BIT;
Fenw(int n = 0) : n(n), BIT(n, 0) {}
int query(int idx) {
int r = 0; for (int i = idx; i >= 0; i = (i&(i+1))-1) r += BIT[i];
return r;
}
void increase(int r, int delta) {
for (int i = r; i < n; i |= i+1) BIT[i] += delta;
}
void update(int l, int r, int delta) {
increase(l, delta); increase(r+1, -delta);
}
};
int n; vi h, idx, ridx, first_left, first_right, delta_left, delta_right;
SegTree st, st2;
void init(int N, vi H) {
n = N; h = H; first_left.assign(n, -1), first_right.assign(n, n);
delta_left.assign(n, 0); delta_right.assign(n, 0);
idx.assign(n, 0); iota(all(idx), 0);
sort(all(idx), [&](int i, int j) {return h[i] < h[j];});
ridx.assign(n, 0); for (int i = 0; i < n; i++) ridx[idx[i]] = i;
st = SegTree(n, H); st2 = SegTree(n, idx);
}
int le = -1, ri = -1, d = -1;
bitset<100'000> f, r;
Fenw fenw; vi rleft, rright;
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;
fenw = Fenw(n+1); rleft.assign(n, 0), rright.assign(n, n-1);
for (auto i : idx) {
if (i < le || i > ri) continue;
int prev = rpos(r._Find_next(rpos(i)));
int nxt = f._Find_next(i);
first_left[i] = prev; first_right[i] = min(n, nxt);
bool good = true;
int left = prev < 0 ? INT_MAX : st.query(prev, i+1) - h[i];
int right = nxt >= n ? INT_MAX : st.query(i, nxt+1) - h[i];
delta_left[i] = left;
delta_right[i] = right;
if (prev > -1 && left < d) good = false;
if (nxt < n && right < 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);
int t = R-L+1;
for (int i = L; i <= R; i++) {
int p = first_left[i], q = first_right[i];
// cout << i << " " << p << " " << q << " " << L << " " << R << "\n";
// cout << "i: " << i << " Condition: " << ((delta_left[i] < D) || (delta_right[i] < D)) << " bit is set? " << f[i] << " dl, dr: " << delta_left[i] << " " << delta_right[i] << "\n";
if ((delta_left[i] < D) || (delta_right[i] < D)) t--;
}
return t;
// return f.count();
}
