#include "towers.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "stub.cpp"
#endif
#define ar array
typedef int64_t ll;
//~ #define int ll
const int inf = 1e9 + 7;
const int N = 1e5 + 5;
//~ int first, mount;
//~ vector<int> a, l, r, res;
vector<ar<int, 2>> res;
vector<int> a;
struct ST{
vector<int> tree;
int N;
ST(int N): N(N){
tree.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx){
tree[x] = v;
return;
}
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l){
return -(N << 2);
}
if(lx >= l && rx <= r){
return tree[x];
}
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get(int l, int r){
return get(l, r, 0, N, 1);
}
}Max(N), Min(N);
void init(int n, vector<int> h) {
a = h;
vector<int> pos;
for(int i=0;i<n;i++){
Max.set(i, a[i]);
if((!i || a[i] < a[i - 1]) && (i + 1 == n || a[i] < a[i + 1])){
pos.push_back(i);
}
}
set<int> ss;
multiset<ar<int, 2>> dif;
for(int i=0;i<(int)pos.size();i++){
if(i){
//~ a[pos[i]] a[pos[i - 1]]
int mx = Max.get(pos[i - 1], pos[i]);
dif.insert({mx - a[pos[i - 1]], pos[i - 1]});
dif.insert({mx - a[pos[i]], pos[i]});
}
ss.insert(pos[i]);
}
//~ for(auto x : ss){
//~ cout<<x<<" ";
//~ }
//~ cout<<"\n";
while(!dif.empty()){
auto [d, i] = *dif.begin();
res.push_back({d, i});
//~ cout<<i<<" "<<d<<"\n";
auto it = ss.lower_bound(i);
auto R = it; R++;
if(it == ss.begin() || R == ss.end()){
if(it == ss.begin()){
int mx = Max.get(*it, *R);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*R], *R}));
} else {
auto L = it; L--;
int mx = Max.get(*L, *it);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*L], *L}));
}
ss.erase(it);
continue;
}
auto L = it; --L;
int mx = Max.get(*L, *it);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*L], *L}));
mx = Max.get(*it, *R);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*R], *R}));
mx = Max.get(*L, *R);
dif.insert({mx - a[*L], *L});
dif.insert({mx - a[*R], *R});
ss.erase(it);
}
res.push_back({inf, *ss.begin()});
//~ for(auto x : res) cout<<x[0]<<" ";
//~ cout<<"\n";
for(int i=1;i<(int)res.size();i++){
assert(res[i - 1][0] <= res[i][0]);
}
}
int max_towers(int l_, int r_, int d) {
int n = a.size();
//~ assert(l_ == 0 && r_ == n - 1);
int j = lower_bound(res.begin(), res.end(), (ar<int, 2>){d, 0}) - res.begin();
return (int)res.size() - j;
}
