#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>;
using pi = pair<int, int>;
/*
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 query_root 0, 0, n
int n; vi arr; vector<pi> st;
SegTree() {}
SegTree(int n, vi arr) : n(n), arr(arr), st(4*n, make_pair(INT_MIN, INT_MAX)) {build(query_root);}
pi combine(pi a, pi b) {return {max(a.first, b.first), min(a.second, b.second)};}
pi build(int i, int l, int r) {
if (is_leaf) return st[i] = {arr[l], arr[l]};
return st[i] = combine(build(left_child), build(right_child));
}
int query(int ql, int qr, bool max = true) {auto v = query(query_root, ql, qr); return max ? v.first : v.second;}
pi query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return {INT_MIN, INT_MAX};
if (ql <= l && r <= qr) return st[i];
return combine(query(left_child, ql, qr), query(right_child, ql, qr));
}
};
const int MAXN = 100'000;
SegTree st;
int n; vi h, idx, first_left, first_right;
int delta_left[MAXN], delta_right[MAXN];
bitset<100'000> f, r;
int rpos(int i) {return r.size() - i - 1;}
vi c1, c2, c3, c4;
void init(int N, vi H) {
n = N; h = H; idx.assign(n, 0); iota(all(idx), 0);
first_left.assign(n, 0); first_right.assign(n, 0);
sort(all(idx), [&](int i, int j) {return h[i] < h[j];});
st = SegTree(n, H);
}
int dv = -1;
bool computed = false;
vi sol;
SegTree st1, st2;
void compute(int D) {
f &= 0; r &= 0;
sol.clear(); c1.clear(); c2.clear(); c3.clear(); c4.clear();
dv = D; computed = true;
for (auto i : idx) {
int prev = rpos(r._Find_next(rpos(i)));
int nxt = f._Find_next(i);
first_left[i] = prev; first_right[i] = min(n, nxt);
int left = prev < 0 ? 1e9 : st.query(prev, i+1) - h[i];
int right = nxt >= n ? 1e9 : st.query(i, nxt+1) - h[i];
delta_left[i] = left; delta_right[i] = right;
f.set(i), r.set(rpos(i));
if (first_left[i] >= 0 && first_right[i] <= n-1 && min(left, right) >= D) c1.push_back(i), sol.push_back(i);
else if (first_left[i] < 0 && first_right[i] <= n-1 && right >= D) c2.push_back(i), sol.push_back(i);
else if (first_left[i] >= 0 && first_right[i] > n-1 && left >= D) c3.push_back(i), sol.push_back(i);
else if (first_left[i] < 0 && first_right[i] >= n) sol.push_back(i);
// if (first_left[i] >= 0 && first_right[i] <= n-1) c1.push_back(min(delta_left[i], delta_right[i]));
// else if (first_left[i] < 0 && first_right[i] <= n-1) c2.push_back(delta_right[i]);
// else if (first_left[i] >= 0 && first_right[i] > n-1) c3.push_back(delta_left[i]);
// else c4.push_back(i);
}
st1 = SegTree(n, first_left), st2 = SegTree(n, first_right);
sort(all(sol));
sort(all(c1)); sort(all(c2)); sort(all(c3)); sort(all(c4));
}
/*
how much structure can be exploited ?!?
sort by 1 axis
persistent segment tree / line sweep over another axis
range queries over a third axis
(a) sort by first_left[i], have a pst over first_right[i], then query how many values >= D ?!? (sounds like persistent merge sort, but 2gb limit ig)
(b)
*/
int max_towers(int L, int R, int D) {
if (!computed) compute(D);
// for (auto &el : sol) cout << el << " "; cout << "\n";
int t = 0, le = lower_bound(all(sol), L) - bg(sol), ri = upper_bound(all(sol), R) - bg(sol) - 1;
t = ri-le+1;
if (le > ri) return 1;
if (st2.query(L, first_left[le], false) < le) t++;
if (st1.query(first_right[ri]+1, R+1, true) > ri) t++;
// t += c1.end() - lower_bound(all(c1), D);
// t += c2.end() - lower_bound(all(c2), D);
// t += c3.end() - lower_bound(all(c3), D);
// t += c4.size();
// for (int i = L; i <= R; i++) {
// if (first_left[i] >= L && first_right[i] <= R && min(delta_left[i], delta_right[i]) >= D) t++;
// if (first_left[i] < L && first_right[i] <= R && delta_right[i] >= D) t++;
// if (first_left[i] >= L && first_right[i] > R && delta_left[i] >= D) t++;
// if (first_left[i] < L && first_right[i] > R) t++;
// // if ((first_left[i] < L || delta_left[i] >= D) && (first_right[i] > R || delta_right[i] >= D)) t++;
// }
return t;
}
