#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxl = 20;
int lt[maxn],rt[maxn],mn[maxn];
vector<int> edge[maxn];
vector<pair<int,int>> res;
void init(int N, std::vector<int> H){
vector<int> v;
for(int i=0;i<N;i++){
while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
lt[i]=(v.empty()?-1:v.back());
v.push_back(i);
}
v.clear();
for(int i=N-1;i>=0;i--){
while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
rt[i]=(v.empty()?-1:v.back());
v.push_back(i);
}
int root=-1;
for(int i=0;i<N;i++){
if(lt[i]==-1 && rt[i]==-1) root=i;
else if(lt[i]==-1 || (rt[i]!=-1 && H[rt[i]]<H[lt[i]])) edge[rt[i]].push_back(i);
else edge[lt[i]].push_back(i);
}
function<void(int,int)> dfs = [&](int u,int p){
mn[u]=u;
for(int v:edge[u]){
dfs(v,u);
if(H[mn[v]]<H[mn[u]]) mn[u]=mn[v];
}
res.push_back({H[u]-H[mn[u]],1});
if(p!=-1) res.push_back({H[p]-H[mn[u]],-1});
};
dfs(root,-1);
sort(res.begin(),res.end());
for(int i=1;i<(int)res.size();i++) res[i].second+=res[i-1].second;
}
int max_towers(int L, int R, int D){
int pos=lower_bound(res.begin(),res.end(),make_pair(D,0))-res.begin()-1;
return res[pos].second;
}
