#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[100100], mn[100100];
priority_queue<int> pq;
vector<int> G;
struct Seg{
pair<int, int> tree[200200];
int sz;
void init(int n){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz};
for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
pair<int, int> query(int l, int r){
++r;
pair<int, int> ret = {-1, 0};
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = max(ret, tree[l++]);
if (r&1) ret = max(ret, tree[--r]);
}
return ret;
}
}tree;
int dnc(int l, int r){
if (l>r) return -1;
if (l==r) {mn[l] = a[l]; return l;}
auto [mx, mid] = tree.query(l, r);
int L = dnc(l, mid-1), R = dnc(mid+1, r);
if (L==-1){
mn[mid] = mn[R];
}
else if (R==-1){
mn[mid] = mn[L];
}
else{
mn[mid] = min(mn[L], mn[R]);
pq.push(mx - max(mn[L], mn[R]));
}
//printf("%d %d -> %d / %d\n", l, r, mid, mn[mid]);
return mid;
}
void init(int N, std::vector<int> H) {
n = N;
for (int i=1;i<=n;i++) a[i] = H[i-1];
tree.init(n+1);
dnc(1, n);
while(!pq.empty()){
G.push_back(pq.top()); pq.pop();
}
reverse(G.begin(), G.end());
//for (auto &x:G) printf("%d ", x);
//printf("\n");
}
int max_towers(int l, int r, int D) {
++l, ++r;
int sz = G.size();
return sz - (lower_bound(G.begin(), G.end(), D) - G.begin()) + 1;
}
