#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<int> R, L;
int idx;
int N;
const int MAXN = 2e5;
vector<int> ps;
struct RMQ {
vector<int> tree;
int n;
RMQ(int n) {
this->n = n;
tree = vector<int>(4 * n);
}
void update(int i, int l, int r, int qp, int val) {
if (l == r) {
tree[i] = val;
return;
}
int m = (l + r) / 2;
if (qp <= m) update(i * 2, l, m, qp, val);
else update(i * 2 + 1, m + 1, r, qp, val);
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
void update(int qp, int val) {
update(1, 1, n, qp, val);
}
int query(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return 0;
if (ql <= l && r <= qr) {
return tree[i];
}
int m = (l + r) / 2;
return max(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
}
int query(int ql, int qr) {
return query(1, 1, n, ql, qr);
}
} seg(MAXN + 1);
vector<int> req;
void init(int _N, std::vector<int> _H) {
N = _N;
a.push_back(0);
vector<array<int, 2>> ord;
for (int i = 1; i <= N; ++i) {
a.push_back(_H[i - 1]);
seg.update(i, a[i]);
ord.push_back({a[i], i});
}
sort(begin(ord), end(ord));
set<int> st;
st.insert(0);
st.insert(N + 1);
for (auto [u, i] : ord) {
auto it = st.lower_bound(i);
int r = *it;
--it;
int l = *it;
if (l == 0 && r == N + 1) {
req.push_back(1e9 + 1);
st.insert(i);
continue;
}
int mxL = 1e9 + 1;
if (l != 0) {
mxL = seg.query(l + 1, i - 1) - u;
}
int mxR = 1e9 + 1;
if (r != N + 1) {
mxR = seg.query(i + 1, r - 1) - u;
}
int mx = min(mxR, mxL);
// if (mx <= 0) continue;
st.insert(i);
req.push_back(mx);
}
sort(begin(req), end(req));
// for (auto& u : req) {
// cerr << u << " ";
// }
// cerr << "\n";
}
int max_towers(int l, int r, int D) {
int i = lower_bound(begin(req), end(req), D) - begin(req);
i = (int)req.size() - i;
return i;
}
