// In the name of Allah
#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define Mp make_pair
#define pb push_back
#define endl '\n'
#define sep ' '
const int maxn = 2e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;
int n;
ll A[maxn]; int L[maxn], R[maxn];
int rmq[maxn][maxlg];
vector<ll> arr; ll sm[maxn];
int GI(ll x) {
return lower_bound(all(arr), x) - arr.begin();
}
ll get_max(int l, int r) {
if (l >= r) return -oo;
int j = __lg(r - l);
return max(rmq[l][j], rmq[r - (1 << j)][j]);
}
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < n; i++) A[i] = H[i];
for (int i = n - 1; i >= 0; i--) {
rmq[i][0] = A[i];
for (int j = 1; j < maxlg; j++) {
if (i + (1 << j) - 1 >= n) break;
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 0; i < n; i++) {
for (L[i] = i - 1; L[i] != -1 && A[i] <= A[L[i]]; L[i] = L[L[i]]);
}
for (int i = n - 1; i >= 0; i--) {
for (R[i] = i + 1; R[i] != n && A[i] <= A[R[i]]; R[i] = R[R[i]]);
}
arr.pb(oo);
for (int i = 0; i < n; i++) {
if (L[i] != -1) {
ll valx = get_max(L[i] + 1, i + 1) - A[i];
if (valx >= 1) arr.pb(valx);
}
if (R[i] != n) {
ll valx = get_max(i, R[i]) - A[i];
if (valx >= 1) arr.pb(valx);
}
}
sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
for (int i = 0; i < n; i++) {
ll x = oo;
if (L[i] != -1) x = min(x, get_max(L[i] + 1, i + 1) - A[i]);
if (R[i] != n) x = min(x, get_max(i, R[i]) - A[i]);
if (x == 0) continue;
int j = GI(x); sm[j]++;
}
for (int j = len(arr) - 2; j >= 0; j--) sm[j] += sm[j + 1];
}
int max_towers(int L, int R, int D) {
int j = lower_bound(all(arr), D) - arr.begin();
return sm[j];
}
