// #pragma once
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif
const int MAX = 1000000000;
const int LOG = 18;
struct Node{
Node* lft, *rgt;
int sum;
Node(){lft = rgt = NULL; sum = 0;}
};
Node* add(Node* rt, int x, int s = 0, int e = MAX){
Node* rt2 = new Node();
Node* ret = rt2;
while(true){
rt2->sum = (rt ? rt->sum: 0) + 1;
if(s == e) break;
int mid = (s + e) / 2;
if(x <= mid){
rt2->rgt = rt ? rt->rgt: NULL;
rt2->lft = new Node();
rt2 = rt2->lft;
if(rt) rt = rt->lft;
e = mid;
} else{
rt2->lft = rt ? rt->lft: NULL;
rt2->rgt = new Node();
rt2 = rt2->rgt;
if(rt) rt = rt->rgt;
s = mid + 1;
}
}
return ret;
}
int getNum(Node* rt, int L, int R, int s = 0, int e = MAX){
if(!rt) return 0;
if(L > e || R < s) return 0;
if(s >= L && e <= R) return rt->sum;
int mid = (s + e) >> 1;
return getNum(rt->lft, L, R, s, mid) + getNum(rt->rgt, L, R, mid + 1, e);
}
// 0-indexed
template<class T>
struct sparse_table{
vector<vector<T>> arr;
vector<int> floorlog;
function<T(T, T)> func;
int n;
sparse_table(){}
sparse_table(vector<T> & vec, function<T(T, T)> f) : n(sz(vec)), floorlog(sz(vec) + 1), func(f){
for(int i = 0; (1 << i) <= n; i++){
for(int j = (1 << i); j < (1 << (i + 1)) && j <= n; j++)
floorlog[j] = i;
}
arr.assign(floorlog[n] + 1, vector<T>(n));
for(int i = n - 1; i >= 0; i--){
arr[0][i] = vec[i];
for(int j = 1; i + (1 << j) <= n; j++){
arr[j][i] = func(arr[j - 1][i], arr[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int i, int j){
int k = floorlog[j - i + 1];
return func(arr[k][i], arr[k][j - (1 << k) + 1]);
}
};
struct Tree{
int n;
vector<Node*> root_seg;
vector<vector<int>> jump;
vector<int> par;
Tree(){}
Tree(int n): n(n), par(n+1), root_seg(n+1, NULL){}
void get_jumps(){
root_seg[n] = new Node();
jump.resize(LOG);
par[n] = n;
jump[0] = par;
for(int i = 0; i < n; i++) if(jump[0][i] == -1) jump[0][i] = n;
jump[0][n] = n;
for(int j = 1; j < LOG; j++){
jump[j].resize(n + 1);
for(int i = 0; i <= n; i++) jump[j][i] = jump[j - 1][jump[j - 1][i]];
}
}
};
// global variables
vector<int> H, V;
sparse_table<int> st, st_ind;
Tree TL, TR, T0;
int n;
int getMin(int L, int R){
if(L > R)swap(L, R);
return st.get(L, R);
}
void init(int N, std::vector<int> HH){
H = HH;
H.push_back(MAX+10);
n = N;
vector<int> ids(n);
iota(ids.begin(), ids.end(), 0);
st = sparse_table<int>(H, [](int i, int j){return min(i, j);});
st_ind = sparse_table<int>(ids, [](int i, int j){return H[i] > H[j] ? i : j;});
TL = Tree(n); TR = Tree(n);
T0 = Tree(n);
stack<int> stk;
Node* zero = new Node();
for(int i = 0; i < n; i++){
while(!stk.empty() && H[stk.top()] < H[i]) stk.pop();
TL.par[i] = stk.empty() ? -1: stk.top();
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i = n - 1; i >= 0; i--){
while(!stk.empty() && H[stk.top()] < H[i]) stk.pop();
TR.par[i] = stk.empty() ? n: stk.top();
stk.push(i);
}
V.resize(n);
for(int i = 0; i < n; i++){
int L = TL.par[i], R = TR.par[i];
int mn = max(getMin(L + 1, i), getMin(i, R - 1));
int D_max = max(0, H[i] - mn);
V[i] = D_max;
T0.root_seg[i] = add(i == 0 ? zero: T0.root_seg[i - 1], D_max);
TL.root_seg[i] = add(TL.par[i] == -1 ? zero: TL.root_seg[TL.par[i]], D_max);
}
for(int i = n - 1; i >= 0; i--){
TR.root_seg[i] = add(TR.par[i] == n ? zero: TR.root_seg[TR.par[i]], V[i]);
}
TL.get_jumps(); TR.get_jumps();
}
int fix_seq(const Tree& T, int mx_H, int i, int D){
// sequence i -> par[i] -> .. till height < mx_H
// subtract for those j in this sequence where getMin(i, j) > H[j] - D
if(H[i] >= mx_H) return 0;
int j = i;
for(int k = LOG - 1; k >= 0; k--){
int p = T.jump[k][j];
if(H[p] < mx_H && getMin(i, p) > H[p] - D) j = p;
}
j = T.jump[0][j];
return getNum(T.root_seg[i], D, MAX) - getNum(T.root_seg[j], D, MAX);
}
int max_towers(int L, int R, int D){
int ret = 1 + getNum(T0.root_seg[R], D, MAX) - (L == 0 ? 0: getNum(T0.root_seg[L - 1], D, MAX));
int mx = st_ind.get(L, R);
ret -= V[mx] >= D;
ret += H[mx] - max(getMin(L, mx), getMin(mx, R)) >= D;
ret -= fix_seq(TR, H[mx], L, D);
ret -= fix_seq(TL, H[mx], R, D);
return ret;
}
