#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int L = 22;
int n, a[N], pl[N], pr[N], ord[N];
bool cmp(int i, int j) { return a[i] < a[j]; }
int mx[N][L], logs[N];
int qmx(int l, int r) {
int k = logs[r - l + 1];
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void buildST() {
for (int i = 1; i <= n; i++) mx[i][0] = a[i];
for (int i = 2; i <= n; i++) logs[i] = logs[i >> 1] + 1;
for (int j = 1; j < L; j++)
for (int i = 1; i + (1 << j) <= n + 1; i++)
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
vector<int> qs;
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; i++) a[i] = H[i - 1];
vector <int> stk;
for (int i = 1; i <= n; i++) {
while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
pl[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
stk.clear();
for (int i = n; i >= 1; i--) {
while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
pr[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
buildST();
for (int i = 1; i <= n; i++) ord[i] = i;
sort(ord + 1, ord + n + 1, cmp);
for (int _i = 2; _i <= n; _i++) {
int i = ord[_i];
int D = 1e9;
if (pl[i] != -1) D = min(D, qmx(pl[i] + 1, i) - a[i]);
if (pr[i] != -1) D = min(D, qmx(i, pr[i] - 1) - a[i]);
qs.push_back(D);
// printf("i=%d delta->%d\n", i, D);
}
sort(qs.begin(), qs.end());
}
int max_towers(int L, int R, int D) {
int res = 1 + qs.end() - lower_bound(qs.begin(), qs.end(), D);
return res;
}
/*
7 1
10 20 60 40 50 30 70
0 6 17
*/
