#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 5;
struct pstNode{
int sum, mn, mx;
};
struct segNode{
int mn, mx, dif1, dif2, locMn;
};
pstNode comb(pstNode a, pstNode b){
return {a.sum + b.sum, min(a.mn, b.mn), max(a.mx, b.mx)};
};
segNode comb(segNode a, segNode b){
return {
min(a.mn, b.mn),
max(a.mx, b.mx),
max({a.dif1, b.dif1, b.mx - a.mn}),
max({a.dif2, b.dif2, a.mx - b.mn}),
(a.mn < b.mn ? a.locMn : b.locMn)
};
}
struct persistentSegTree{
pstNode seg[mx * 31]; int idx = 1, lc[mx * 31] = {}, rc[mx * 31] = {};
persistentSegTree(){
fill(seg, seg + mx * 31, pstNode({0, int(1e9), 0}));
}
void dup(int &i){
lc[idx] = lc[i];
rc[idx] = rc[i];
seg[idx] = seg[i];
i = idx; idx++;
}
void upd(int p, int &i, int l = 0, int r = mx){
dup(i);
if (l == r){ seg[i] = {1, l, l}; return; }
int mid = (l + r) / 2;
if (p <= mid) upd(p, lc[i], l, mid);
else upd(p, rc[i], mid + 1, r);
seg[i] = comb(seg[lc[i]], seg[rc[i]]);
}
pstNode qry(int ql, int qr, int i, int l = 0, int r = mx){
if (qr < l or ql > r or !i) return {0, int(1e9), 0};
if (l >= ql and r <= qr) return seg[i];
int mid = (l + r) / 2;
return comb(qry(ql, qr, lc[i], l, mid), qry(ql, qr, rc[i], mid + 1, r));
}
};
struct segTree{
segNode seg[mx * 2 + 5];
void upd(int i, int val){
seg[i + mx] = {val, val, 0, 0, i};
for (i = (i + mx) / 2; i > 0; i /= 2)
seg[i] = comb(seg[i * 2], seg[i * 2 + 1]);
}
segNode qry(int l, int r){
segNode retL = segNode({int(1e9), 0, 0, 0, 0});
segNode retR = segNode({int(1e9), 0, 0, 0, 0});
for (l += mx, r += mx; l <= r; r /= 2, l /= 2){
if (l % 2 == 1) retL = comb(retL, seg[l++]);
if (r % 2 == 0) retR = comb(seg[r--], retR);
}
return comb(retL, retR);
}
};
struct sparseTable{
int rmq[mx][17];
void build(vector<int> A){
for (int j = 0; j < 17; j++)
for (int i = 0; i + (1 << j) - 1 < A.size(); i++)
rmq[i][j] = !j ? A[i] : max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
int qry(int l, int r){
int lg = 31 - __builtin_clz(r - l + 1);
return max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]);
}
};
vector<int> H; map<int, int> root; segTree st; persistentSegTree pst; sparseTable fastMax;
int max_towers(int l, int r, int d){
auto it = root.lower_bound(d);
pstNode ret = pst.qry(l, r, it->second);
if (ret.sum == 0){
ret.mn = ret.mx = st.qry(l, r).locMn;
ret.sum = 1;
}
int lo = l, hi = ret.mn;
while (lo < hi){
int mid = (lo + hi + 1) / 2;
(fastMax.qry(mid, ret.mn) >= H[ret.mn] + d ? lo = mid : hi = mid - 1);
}
ret.sum += (H[lo] >= H[ret.mn] + d and st.qry(l, lo).dif1 >= d);
lo = ret.mx, hi = r;
while (lo < hi){
int mid = (lo + hi) / 2;
(fastMax.qry(ret.mx, mid) >= H[ret.mx] + d ? hi = mid : lo = mid + 1);
}
ret.sum += (H[hi] >= H[ret.mx] + d and st.qry(hi, r).dif2 >= d);
return ret.sum;
}
void init(int n, vector<int> h_){
H = h_;
fastMax.build(H);
int L[n], R[n];
for (int i = 0; i < n; i++) L[i] = R[i] = -1;
stack<int> stk;
for (int i = 0; i < n; i++){
st.upd(i, H[i]);
while (stk.size() and H[stk.top()] >= H[i]){
R[stk.top()] = i;
stk.pop();
}
if (stk.size()) L[i] = stk.top();
stk.push(i);
}
vector<pair<int, int>> V;
for (int i = 0; i < n; i++){
int dlim = 1e9;
if (L[i] != -1) dlim = min(dlim, fastMax.qry(L[i], i) - H[i]);
if (R[i] != -1) dlim = min(dlim, fastMax.qry(i, R[i]) - H[i]);
V.push_back({dlim, i});
}
sort(V.begin(), V.end(), greater<pair<int, int>>());
int curRoot = 1;
for (auto [dlim, i] : V){
pst.upd(i, curRoot);
root[dlim] = curRoot;
}
}
