#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"
const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;
int n;
int a[maxn];
int l[maxn];
int r[maxn];
int f[maxn];
void init(int N, std::vector<int> H) {
n = N;
for(int i = 1; i <= n; i++){
a[i] = H[i-1];
} vector<int> v;
for(int i = 1; i <= n; i++){
while(v.size() && a[v.back()] > a[i]){
l[i] = max({l[i], l[v.back()], a[v.back()]});
v.pop_back();
} if(v.empty()) l[i] = inf * 2;
v.push_back(i);
} v.clear();
for(int i = n; i > 0; i--){
while(v.size() && a[v.back()] > a[i]){
r[i] = max({r[i], r[v.back()], a[v.back()]});
v.pop_back();
} if(v.empty()) r[i] = inf * 2;
v.push_back(i);
f[i] = min(l[i], r[i]) - a[i];
} sort(f + 1, f + n + 1, greater<int>());
}
int max_towers(int L, int R, int D) {
L++; R++;
int ans = 1;
for(int l = 2, r = n; l <= r; ){
int mid = (l + r) >> 1;
if(f[mid] < D) r = mid - 1;
else l = mid + 1, ans = mid;
} return ans;
}
