#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5, half = 1e5+1;
int n, a[MAXN],segt[200003],psum[MAXN+1];
vector<pair<int,int>> answers;
int query(int l, int r){
l += half;
r += half;
int ans = 0;
while (l <= r){
if (l&1){
ans = max(ans,segt[l]);
l++;
}
if (r%2 == 0){
ans = max(ans,segt[r]);
r--;
}
l >>= 1;
r >>= 1;
}
return ans;
}
void modify(int node, int val){
node += half;
segt[node] = val;
node >>= 1;
while (node){
segt[node] = max(segt[2*node],segt[2*node+1]);
node >>= 1;
}
}
void init(int N, vector<int> H){
n = N;
for (int i=0; i<n; ++i){
a[i] = H[i];
modify(i,a[i]);
}
for (int i=0; i<n; ++i){
if ((i == 0 or a[i] < a[i-1]) and (i == n-1 or a[i] < a[i+1])){
psum[i+1]++;
}
psum[i+1] += psum[i];
}
vector<pair<int,int>> v,deltas;
for (int i=0; i<n; ++i){
v.emplace_back(a[i],i);
}
sort(v.begin(),v.end());
set<int> pos = {INT_MIN,INT_MAX};
for (auto i:v){
auto it = pos.upper_bound(i.second);
int A = *it,maxi=INT_MAX;
it--;
int B = *it;
bool ok = false;
if (A != INT_MAX){
if (i.second == A-1) ok = true;
maxi = min(maxi,query(i.second,A));
}
if (B != INT_MIN){
if (B == i.second-1) ok = true;
maxi = min(maxi,query(B,i.second));
}
if (maxi != i.first and !ok){
if (maxi == INT_MAX) deltas.emplace_back(maxi,i.second);
else deltas.emplace_back(max(1,maxi-i.first),i.second);
}
pos.emplace(i.second);
}
sort(deltas.rbegin(),deltas.rend());
int val = INT_MAX, occ = 0;
for (auto i:deltas){
if (val == i.first){
++occ;
}
else{
answers.emplace_back(val,occ);
val = i.first;
occ++;
}
}
answers.emplace_back(val,occ);
reverse(answers.begin(),answers.end());
}
int max_towers(int L, int R, int D){
if (L == 0 and R == n-1){
int idx = lower_bound(answers.begin(),answers.end(),make_pair(D,0))-answers.begin();
return answers[idx].second;
}
if (D == 1){
int ans = 0;
if (L < R and a[L] < a[L+1]) ++ans;
if (L < R and a[R] < a[R-1]) ++ans;
L++; R++;
if (L == R) return 1;
return psum[R-1]-psum[L]+ans;
}
set<int> st;
vector<pair<int,int>> v;
for (int i=L; i<=R; ++i){
v.emplace_back(a[i],i);
}
sort(v.begin(),v.end());
int ans = 0;
for (auto k:v){
int i = k.second;
if (st.empty()){
st.emplace(i);
++ans;
continue;
}
auto it = st.upper_bound(i);
int A = *it;
--it;
int B = *it;
if ((*st.rbegin() < i or query(i,A)-D >= max(a[A],a[i])) and (*st.begin() > i or query(B,i)-D >= max(a[B],a[i]))){
st.emplace(i);
++ans;
}
}
return ans;
}
