#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 10;
const int LOG = 17;
int L[N], R[N];
int tab[LOG][N];
int G[N];
int n;
int H[N];
int get_max(int l, int r){
int sz = (r - l + 1);
return max(tab[G[sz]][l], tab[G[sz]][r - (1 << G[sz]) + 1]);
}
vector<int> lis;
void init(int _n, vector<int> _H) {
n = _n;
for(int i = 0 ; i < n; i ++ ){
L[i] = R[i] = -1;
H[i] = _H[i];
}
vector<int> ord;
for(int i = 0 ; i < n; i ++ ){
tab[0][i] = H[i];
// ------------------
while(!ord.empty() && H[ord.back()] > H[i]){
R[ord.back()] = i;
ord.pop_back();
}
if(!ord.empty()){
L[i] = ord.back();
}
ord.push_back(i);
}
for(int ln = 1; ln < LOG; ln ++ ){
for(int i = 0 ; i < n; i ++){
if((i + (1 << ln) - 1) < n){
tab[ln][i] = max(tab[ln - 1][i], tab[ln - 1][i + (1 << (ln - 1))]);
}
}
}
int lg = 0;
for(int sz = 1; sz <= n; sz ++ ){
while((1 << (lg + 1)) <= sz){
lg ++ ;
}
G[sz] = lg;
}
int maxi;
int need;
for(int i = 0; i < n; i ++ ){
need = (int)1e9;
if(L[i] != -1){
need = min(need, get_max(L[i],i)-H[i]);
}
if(R[i] != -1){
need = min(need, get_max(i,R[i])-H[i]);
}
lis.push_back(need);
}
sort(lis.begin(), lis.end());
}
int solve(int l, int r, int delta, int bound){
if(l>r) return 0;
int big = l;
bool emp = true;
for(int i = l ; i <= r; i ++ ){
if(H[i] > H[big]) big = i;
if(H[i] <= bound){
emp = false;
}
}
if(emp) return 0;
return max(1, solve(l,big-1,delta,H[big]-delta)+solve(big+1,r,delta,H[big]-delta));
}
int max_towers(int L, int R, int delta) {
int id = lower_bound(lis.begin(), lis.end(), delta) - lis.begin();
return (int)lis.size() - id;
}
