#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);
}
};
struct persistent_segtree{
struct Node{
int x;
Node *l = nullptr, *r = nullptr;
Node(int _x = 0): x(_x){}
Node(Node* _l, Node* _r): x(_l->x+_r->x), l(_l), r(_r){}
};
int k = 1;
persistent_segtree(int n){
while(k < n) k<<=1;
}
void init_rec(Node* nd, int a, int b){
if(a == b) return;
nd->l = new Node();
nd->r = new Node();
int md = (a+b)>>1;
init_rec(nd->l, a, md);
init_rec(nd->r, md+1, b);
}
Node* init(){
auto nd = new Node();
init_rec(nd, 0, k-1);
return nd;
}
Node* update(Node* nd, int a, int b, int i, int x){
if(a == b) return new Node(nd->x+x);
int md = (a+b)>>1;
if(i <= md) return new Node(update(nd->l, a, md, i, x), nd->r);
return new Node(nd->l, update(nd->r, md+1, b, i, x));
}
Node* update(Node* nd, int i, int x){
return update(nd, 0, k-1, i, x);
}
int sum(Node* nd, int a, int b, int l, int r){
if(a > r || b < l) return 0;
if(a >= l && b <= r) return nd->x;
int md = (a+b)>>1;
return sum(nd->l, a, md, l, r)+sum(nd->r, md+1, b, l, r);
}
int sum(Node* nd, int l, int r){
if(l > r) return 0;
return sum(nd, 0, k-1, l, r);
}
int first_one(Node* nd, int l, int r, int a, int b){
if(a > r || b < l) return -1;
if(nd->x == 0) return -1;
if(a == b) return a;
int md = (a+b)>>1;
int rt = first_one(nd->l, l, r, a, md);
if(rt == -1) return first_one(nd->r, l, r, md+1, b);
return rt;
}
int first_one(Node *nd, int l, int r){
return first_one(nd, l, r, 0, k-1);
}
int last_one(Node* nd, int l, int r, int a, int b){
if(a > r || b < l) return -1;
if(nd->x == 0) return -1;
if(a == b) return a;
int md = (a+b)>>1;
int rt = last_one(nd->r, l, r, md+1, b);
if(rt == -1) return last_one(nd->l, l, r, a, md);
return rt;
}
int last_one(Node *nd, int l, int r){
return last_one(nd, l, r, 0, k-1);
}
};
int n;
vector<int> h;
segtree seg(0);
vector<int> DL, DR, DLR;
vector<int> SL, SR;
vector<int> cmpr;
map<int, int> mp;
persistent_segtree psL(0), psR(0), psLR(0);
vector<persistent_segtree::Node*> ndL, ndR, ndLR;
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++) cmpr.pb(DL[i]), cmpr.pb(DR[i]);
sort(cmpr.begin(), cmpr.end());
for(int i = 0; i < cmpr.size(); i++) mp[cmpr[i]] = i;
for(int &x: DL) x = mp[x];
for(int &x: DR) x = mp[x];
for(int i = 0; i < n; i++) DLR[i] = min(DL[i], DR[i]);
psL = persistent_segtree(n);
psR = persistent_segtree(n);
psLR = persistent_segtree(n);
ndL.resize(2*n);
ndR.resize(2*n);
ndLR.resize(2*n);
vector<vector<int>> sth(2*n);
ndL[2*n-1] = psL.init();
for(int i = 0; i < n; i++) sth[DL[i]].pb(i);
for(int i = 2*n-1; i >= 0; i--){
if(i+1 < 2*n) ndL[i] = ndL[i+1];
for(int j: sth[i]) ndL[i] = psL.update(ndL[i], j, 1);
sth[i].clear();
}
ndR[2*n-1] = psR.init();
for(int i = 0; i < n; i++) sth[DR[i]].pb(i);
for(int i = 2*n-1; i >= 0; i--){
if(i+1 < 2*n) ndR[i] = ndR[i+1];
for(int j: sth[i]) ndR[i] = psR.update(ndR[i], j, 1);
sth[i].clear();
}
ndLR[2*n-1] = psLR.init();
for(int i = 0; i < n; i++) sth[DLR[i]].pb(i);
for(int i = 2*n-1; i >= 0; i--){
if(i+1 < 2*n) ndLR[i] = ndLR[i+1];
for(int j: sth[i]) ndLR[i] = psLR.update(ndLR[i], j, 1);
sth[i].clear();
}
}
int max_towers(int L, int R, int D){
auto it = lower_bound(cmpr.begin(), cmpr.end(), D);
if(it == cmpr.end()) return 1;
int d = mp[*it];
int ans = psLR.sum(ndLR[d], L, R);
if(ans == 0){
int a = psR.first_one(ndR[d], L, R), b = psL.last_one(ndL[d], L, R);
if(a != -1 && b != -1 && a < b) return 2;
return 1;
}
int a = psLR.first_one(ndLR[d], L, R), b = psLR.last_one(ndLR[d], L, R);
if(psR.sum(ndR[d], L, a-1) > 0) ans++;
if(psL.sum(ndL[d], b+1, R) > 0) ans++;
return ans;
}
