#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 1e5 + 5, INF = 2e9;
int n;
arr<int, N> h;
struct Sgt {
arr<int, 4 * N> tr;
void bld(int u = 1, int lw = 1, int hg = n) {
if (lw == hg) { tr[u] = h[lw]; return; }
int md = (lw + hg) / 2;
bld(2 * u, lw, md), bld(2 * u + 1, md + 1, hg);
tr[u] = max(tr[2 * u], tr[2 * u + 1]);
}
void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
if (lw == hg) { tr[u] += x; return; }
int md = (lw + hg) / 2;
if (i <= md) upd(i, x, 2 * u, lw, md);
else upd(i, x, 2 * u + 1, md + 1, hg);
tr[u] = max(tr[2 * u], tr[2 * u + 1]);
}
int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
if (l > r) return 0;
if (l <= lw && hg <= r) return tr[u];
int md = (lw + hg) / 2, ans = 0;
if (l <= md) ans = max(ans, qry(l, r, 2 * u, lw, md));
if (r > md) ans = max(ans, qry(l, r, 2 * u + 1, md + 1, hg));
return ans;
}
} sgt;
map<int, int> bfr;
set<int> mns;
set<pii> gps;
int dff(int l, int r) {
return sgt.qry(l, r) - max(h[l], h[r]);
}
vec<pii> src;
void init(int _n, vec<int> _h) {
n = _n;
for (int i = 1; i <= n; i++) h[i] = _h[i - 1];
sgt.bld();
for (int i = 1; i <= n; i++)
if ((i == 1 || h[i] < h[i - 1]) && (i == n || h[i] < h[i + 1]))
mns.insert(i);
for (auto it = mns.begin(); it != mns.end(); it++) {
if (next(it, 1) == mns.end()) continue;
gps.insert({dff(*it, *next(it, 1)), *it});
}
while (gps.size()) {
pii x = *gps.begin(); gps.erase(gps.begin());
int i = x.sec;
// cout << x.fir << ": " << mns.size() << '\n';
bfr[x.fir] = mns.size(); // sus
int j = *(++mns.find(i));
if (h[i] < h[j]) {
if (++mns.find(j) == mns.end()) { mns.erase(j); continue;}
int k = *(++mns.find(j));
mns.erase(j), gps.erase({dff(j, k), j});
gps.insert({dff(i, k), i});
} else {
if (mns.find(i) == mns.begin()) { mns.erase(i); continue; }
int k = *(--mns.find(i));
mns.erase(i), gps.erase({dff(k, i), k});
gps.insert({dff(k, j), k});
}
}
bfr[INF] = 1;
for (pii x : bfr) src.push_back(x);
// for (int i : mns) cout << i << '\n';
// for (pii x : gps) cout << x.fir << " " << x.sec << '\n';
// for (pii x : bfr) cout << x.fir << " " << x.sec << '\n';
}
int max_towers(int l, int r, int d) {
l++, r++;
int lw = 0, hg = src.size() - 1;
while (lw < hg) {
int md = (lw + hg) / 2;
if (src[md].fir >= d) hg = md;
else lw = md + 1;
}
return src[lw].sec;
}
