#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h;
int n;
void init(int N, vector<int> H) {
n = N;
h = H;
}
bool processed = false;
vector<int> nxt, dow;
vector<vector<int>> jump;
int max_towers(int l, int r, int D) {
if (!processed) {
processed = true;
deque<pair<int, int>> st;
nxt.assign(n + 1, n);
dow.assign(n + 1, n);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && h[st.front().second] <= h[i]) st.pop_front();
st.push_front({h[i], i});
auto p = lower_bound(st.begin(), st.end(), pair{h[i] + D, -1});
if (p != st.end()) {
nxt[i] = p->second;
}
}
for (int i = n - 2; i >= 0; i--) {
nxt[i] = min(nxt[i], nxt[i + 1]);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && h[st.back().second] >= h[i]) st.pop_back();
st.push_back({h[i], i});
auto p = lower_bound(st.begin(), st.end(), pair{h[i] - D + 1, -1});
if (p != st.begin()) {
p--;
dow[i] = p->second;
}
}
for (int i = n - 2; i >= 0; i--) {
dow[i] = min(dow[i], dow[i + 1]);
}
jump.assign(n + 1, vector<int>(20, n));
for (int i = 0; i < n; i++) {
jump[i][0] = nxt[i];
jump[i][1] = dow[nxt[i]];
}
for (int j = 2; j < 20; j++) {
for (int i = 0; i < n; i++) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
}
int p = l;
int s = 0;
for (int i = 19; i >= 1; i--) {
if (jump[p][i] <= r) {
p = jump[p][i];
s += 1 << i;
}
}
return s / 2 + 1;
}
