#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int n, l[nx], r[nx], rt, dpt[nx], sm, f;
map<int, int> mp;
stack<int> s;
vector<int> h;
set<pair<int, int>> res;
void dfs(int u, int p)
{
if (l[u]!=-1) dfs(l[u], u), dpt[u]=max(dpt[u], dpt[l[u]]+h[u]-h[l[u]]);
if (r[u]!=-1) dfs(r[u], u), dpt[u]=max(dpt[u], dpt[r[u]]+h[u]-h[r[u]]);
if (p!=-1) mp[dpt[u]+1]++, mp[dpt[u]+h[p]-h[u]+1]--;
}
void init(int N, std::vector<int> H) {
h=H;
}
int max_towers(int L, int R, int D) {
if (!f)
{
f=1;
for (int i=L; i<=R; i++)
{
l[i]=r[i]=-1;
while (!s.empty()&&h[s.top()]<h[i]) l[i]=s.top(), s.pop();
if (s.empty()) rt=i;
else r[s.top()]=i;
s.push(i);
}
dfs(rt, -1);
for (auto [x, y]:mp) sm+=y, res.insert({x, sm});
}
if (prev(res.upper_bound({D, 1e9}))->second) return prev(res.upper_bound({D, 1e9}))->second;
return 1;
}
