#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 1e5 + 5;
const int INF = 2e9;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
struct Node{
int cnt, l, r;
Node(){
this->cnt = 0;
this->l = this->r = -1;
}
};
int n, l_min[lim], r_min[lim], h[lim], log_v[lim], spt[lim][17];
vector<Node>st;
vector<pair<int, int>>a(1, make_pair(INF, -1));
int get_max(int l, int r){
int k = log_v[r - l + 1];
return max(spt[l][k], spt[r - (1 << k) + 1][k]);
}
void update(int id, int p){
int l = 1, r = n;
while(l < r){
st[id].cnt++;
int m = (l + r) >> 1;
if(m < p){
st.emplace_back(st[st[id].r]);
st[id].r = int(st.size()) - 1;
id = st[id].r;
l = m + 1;
}
else{
st.emplace_back(st[st[id].l]);
st[id].l = int(st.size()) - 1;
id = st[id].l;
r = m;
}
}
st[id].cnt++;
}
void build(int id = 0, int l = 1, int r = n){
if(l == r){
return;
}
st[id].l = st.size();
st.emplace_back(Node());
st[id].r = st.size();
st.emplace_back(Node());
int m = (l + r) >> 1;
build(st[id].l, l, m);
build(st[id].r, m + 1, r);
}
void init(int N, vector<int>H){
log_v[0] = -1;
for(int i = 1; i < lim; i++){
log_v[i] = log_v[i >> 1] + 1;
}
n = N;
for(int i = 0; i < n; i++){
spt[i + 1][0] = h[i + 1] = H[i];
}
for(int j = 1; j < 17; j++){
for(int i = 1; i + (1 << j) - 1 <= n; i++){
spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
}
}
stack<int>stk;
for(int i = 1; i <= n; stk.push(i++)){
while(!stk.empty() && h[i] < h[stk.top()]){
stk.pop();
}
l_min[i] = (stk.empty() ? 0 : stk.top());
}
while(!stk.empty()){
stk.pop();
}
for(int i = n; i > 0; stk.push(i--)){
while(!stk.empty() && h[i] < h[stk.top()]){
stk.pop();
}
r_min[i] = (stk.empty() ? n + 1 : stk.top());
}
for(int i = 1; i <= n; i++){
a.emplace_back(min(l_min[i] == 0 ? INF : get_max(l_min[i] + 1, i), r_min[i] == n + 1 ? INF : get_max(i, r_min[i] - 1)) - h[i], i);
}
sort(a.begin(), a.end(), greater<pair<int, int>>());
st.assign(n + 1, Node());
build();
for(int i = 1; i <= n; i++){
st[i] = st[i - 1];
update(i, a[i].second);
}
}
int max_towers(int l, int r, int d){
int low = 1, high = n, id = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(a[mid].first >= d){
low = (id = mid) + 1;
}
else{
high = mid - 1;
}
}
return st[id].cnt;
}
