#include "towers.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
namespace
{
int N;
vector<int> H, p, l, r, vis;
map<int, int> mp;
}
void init(int _N, vector<int> _H)
{
N = _N;
H = _H;
H.emplace_back(2e9);
p = vector<int>(N + 1, 0);
vector<int> l = p, r = p, vis = p;
vector<int> mono = {N};
for (int i = 0; i <= N; i++)
{
while (H[mono.back()] < H[i])
r[mono.back()] = i, mono.pop_back();
l[i] = mono.back();
mono.push_back(i);
}
for (int i = 0; i < N; i++)
if (H[l[i]] < H[r[i]])
p[i] = l[i];
else
p[i] = r[i];
p[N] = N + 1;
vector<int> v;
for (int i = 0; i < N; i++)
vis[p[i]] = 1;
for (int i = 0; i < N; i++)
if (!vis[i])
v.emplace_back(i);
sort(v.begin(), v.end(), [&](int i, int j)
{ return H[i] < H[j]; });
for (int i = 0; i <= N; i++)
vis[i] = 0;
vector<int> inc;
for (auto i : v)
{
int c = i, D = 0;
while (c != N + 1)
{
D = H[c] - H[i];
if(vis[c])
break;
vis[c] = 1;
c = p[c];
}
inc.emplace_back(D);
}
sort(inc.begin(), inc.end(), greater<>());
int acc = 0;
for (auto i : inc)
{
acc++;
mp[i] = acc;
}
}
int max_towers(int L, int R, int D)
{
return mp.lower_bound(D)->second;
}
