#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, X = -1;
vector<int> H, pfs, lg;
vector<vector<int>> st;
int query(int l, int r) {
int k = __lg(r - l);
return max(st[l][k], st[r - (1 << k)][k]);
}
void init(int _N, vector<int> _H) {
N = _N;
H = _H;
int L = 0, R = N - 1;
while (L + 1 < N && H[L + 1] > H[L]) L++;
while (R - 1 >= 0 && H[R - 1] > H[R]) R--;
if (L == R) X = L;
pfs.resize(N + 1);
for (int i = 0; i < N; i++) {
pfs[i + 1] = pfs[i];
if ((i == 0 || H[i] < H[i - 1]) && (i == N - 1 || H[i] < H[i + 1])) {
pfs[i + 1]++;
}
}
int lg = __lg(N);
st.assign(N, vector<int>(lg + 1));
for (int i = 0; i < N; i++) {
st[i][0] = H[i];
}
for (int j = 0; j < lg; j++) {
for (int i = 0; i + (2 << j) <= N; i++) {
st[i][j + 1] = max(st[i][j], st[i + (1 << j)][j]);
}
}
}
int subtask1(int L, int R, int D) {
if (L < X && X < R && max(H[L], H[R]) <= H[X] - D) {
return 2;
} else {
return 1;
}
}
int subtask23(int L,int R, int D) {
R++;
vector<int> p(R - L);
iota(p.begin(), p.end(), L);
sort(p.begin(), p.end(), [&](int i, int j) {
return H[i] < H[j];
});
set<int> s;
int ans = 0;
for (int i : p) {
auto it = s.lower_bound(i);
if (it != s.begin()) {
int j = *prev(it);
if (max(H[i], H[j]) > query(j, i + 1) - D) continue;
}
if (it != s.end()) {
int j = *it;
if (max(H[i], H[j]) > query(i, j + 1) - D) continue;
}
ans++;
s.insert(i);
}
return ans;
}
int subtask4(int L, int R, int D) {
if (L == R) return 1;
int ans = pfs[R] - pfs[L + 1];
if (H[L] < H[L + 1]) ans++;
if (H[R] < H[R - 1]) ans++;
return ans;
}
int max_towers(int L, int R, int D) {
if (X != -1) return subtask1(L, R, D);
if (D == 1) return subtask4(L, R, D);
return subtask23(L, R, D);
}
