#include "towers.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 1e5 + 5, inf = 2e18, lg = 17;
ll a[N], n, lef[N], rig[N], up[lg][N];
ll suf[N];
ll mn[N], mn1[N];
bool flg = 0;
void init(int N, vector<int> H)
{
n = N;
for (ll i = 1; i <= n; i++)
a[i] = H[i - 1];
}
void precomp(ll d)
{
vector<pair<ll, ll>> st;
for (ll i = 1; i <= n; i++)
{
while (!st.empty() and a[i] > st.back().first)
st.pop_back();
auto pos = lower_bound(st.begin(), st.end(), make_pair(a[i] + d - 1, inf), greater());
if (pos == st.begin())
lef[i] = 0;
else
lef[i] = (pos - 1)->second;
st.push_back(make_pair(a[i], i));
}
while (!st.empty())
st.pop_back();
for (ll i = n; i >= 1; i--)
{
while (!st.empty() and a[i] > st.back().first)
st.pop_back();
auto pos = lower_bound(st.begin(), st.end(), make_pair(a[i] + d - 1, inf), greater());
if (pos == st.begin())
rig[i] = n + 1;
else
rig[i] = (pos - 1)->second;
st.push_back(make_pair(a[i], i));
}
for (ll i = 1; i <= n; i++)
mn[i] = suf[i] = mn1[i] = n + 2;
for (ll i = 1; i <= n; i++)
mn[lef[i]] = min(mn[lef[i]], rig[i]), mn1[lef[i]] = min(mn1[lef[i]], i), suf[i] = rig[i];
for (ll i = 0; i < lg; i++) up[i][n + 1] = up[i][n + 2] = n + 2;
for (ll i = n - 1; i >= 1; i--)
suf[i] = min(suf[i], suf[i + 1]), mn[i] = min(mn[i + 1], mn[i]), mn1[i] = min(mn1[i + 1], mn1[i]);
for (ll i = n; i >= 1; i--)
{
up[0][i] = mn[i];
for (ll j = 1; j < lg; j++) up[j][i] = up[j - 1][up[j - 1][i]];
}
}
int max_towers(int l, int r, int d)
{
l++, r++;
if (!flg)
precomp(d), flg = 1;
if (suf[l] > r) return 1;
l = suf[l];
ll ans = 1;
for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][l] <= r) ans += 1 << bit, l = up[bit][l];
if (mn1[l] <= r) ans++;
return ans;
}
