#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, H, p, l, r, vis;
}
void init(int _N, vector<int> _H)
{
N = _N;
::_H = _H;
}
int max_towers(int L, int R, int D)
{
H = vector<int>(_H.begin() + L, _H.begin() + R + 1);
N = (int)H.size();
H.emplace_back(2e9);
p = vector<int>(N, 0);
vis = vector<int>(N + 1, 0);
l = r = 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];
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;
int ans = 0;
for (auto i : v)
if (!vis[i])
{
int c = i;
bool flag = 1;
while (c != N)
{
if (H[c] < H[i] + D && vis[c])
flag = 0;
vis[c] = 1;
c = p[c];
}
if (flag)
ans++;
}
return ans;
}
