#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct segtree{
int k = 1;
vector<int> v;
segtree(int n){
while(k < n) k*=2;
v.assign(2*k, 0);
}
void update(int i, int x){
i+=k;
v[i] = x;
i/=2;
while(i){
v[i] = max(v[2*i], v[2*i+1]);
i/=2;
}
}
int get(int l, int r, int nd, int a, int b){
if(a > r || b < l) return 0;
if(a >= l && b <= r) return v[nd];
int md = (a+b)/2;
return max(get(l, r, 2*nd, a, md), get(l, r, 2*nd+1, md+1, b));
}
int get(int l, int r){
if(l > r) return 0;
return get(l, r, 1, 0, k-1);
}
};
int n;
vector<int> h;
segtree seg(0);
vector<int> DL, DR, DLR;
vector<int> SL, SR;
void init(int _n, vector<int> _h){
swap(n, _n);
swap(h, _h);
seg = segtree(n);
DR.assign(n, 1e9);
DL.assign(n, 1e9);
DLR.assign(n, 1e9);
SL.assign(n, 0);
SR.resize(n, n-1);
for(int i = 0; i < n; i++) seg.update(i, h[i]);
stack<int> st;
for(int i = n-1; i >= 0; i--){
while(!st.empty() && h[i] < h[st.top()]){
SL[st.top()] = i;
DL[st.top()] = max(0, seg.get(i, st.top())-h[st.top()]);
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = 0; i < n; i++){
while(!st.empty() && h[i] < h[st.top()]){
SR[st.top()] = i;
DR[st.top()] = max(0, seg.get(st.top(), i)-h[st.top()]);
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = 0; i < n; i++) DLR[i] = min(DL[i], DR[i]);
}
int max_towers(int L, int R, int D){
int ans = 0;
int first = -1, last = -1;
for(int i = L; i <= R; i++){
if(D <= DLR[i]){
ans++;
if(first == -1) first = i;
last = i;
}
}
if(first == -1){
for(int i = L; i <= R; i++) if(D <= DR[i]){
for(int j = R; j > i; j--) if(D <= DL[j]) return 2;
break;
}
return 1;
}
for(int i = L; i < first; i++) if(D <= DR[i]){
ans++;
break;
}
for(int i = last+1; i <= R; i++) if(D <= DL[i]){
ans++;
break;
}
return ans;
}
