#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const int INF = 2e9 + 9;
struct PersistentSegTree {
int n;
vi st, l, r;
PersistentSegTree(int _n) : n(_n), st(1, 0), l(1, 0), r(1, 0) {}
int new_node(int u) {
st.pb(st[u]);
l.pb(l[u]);
r.pb(r[u]);
return sz(st) - 1;
}
int update(int pos, int toAdd, int lo, int hi, int node) {
node = new_node(node);
if (hi - lo == 1) {
st[node] += toAdd;
return node;
}
int mid = (lo + hi) / 2;
if (pos < mid) {
l[node] = update(pos, toAdd, lo, mid, l[node]);
} else {
r[node] = update(pos, toAdd, mid, hi, r[node]);
}
st[node] = st[l[node]] + st[r[node]];
return node;
}
int update(int pos, int toAdd, int root) {
return update(pos, toAdd, 0, n, root);
}
int query(int s, int e, int lo, int hi, int node) {
if (e <= lo || hi <= s) {
return 0;
}
if (s <= lo && hi <= e) {
return st[node];
}
int mid = (lo + hi) / 2;
return query(s, e, lo, mid, l[node]) +
query(s, e, mid, hi, r[node]);
}
int query(int s, int e, int root) {
return query(s, e, 0, n, root);
}
int findFirst(int s, int e, int lo, int hi, int node) {
if (e <= lo || hi <= s || !st[node]) {
return -1;
}
if (hi - lo == 1) {
return lo;
}
int mid = (lo + hi) / 2;
int k = findFirst(s, e, lo, mid, l[node]);
if (k != -1) return k;
return findFirst(s, e, mid, hi, r[node]);
}
int findFirst(int s, int e, int root) {
return findFirst(s, e, 0, n, root);
}
int findLast(int s, int e, int lo, int hi, int node) {
if (e <= lo || hi <= s || !st[node]) {
return -1;
}
if (hi - lo == 1) {
return lo;
}
int mid = (lo + hi) / 2;
int k = findLast(s, e, mid, hi, r[node]);
if (k != -1) return k;
return findLast(s, e, lo, mid, l[node]);
}
int findLast(int s, int e, int root) {
return findLast(s, e, 0, n, root);
}
};
template<typename T>
struct SegTree {
int n;
vector<T> st;
T neutr;
SegTree() {}
SegTree(vector<T> &a, T null) : n(sz(a)), st(2 * n), neutr(null) {
forn(i, n) st[i + n] = a[i];
dforsn(i, 1, n) st[i] = max(st[2 * i], st[2 * i + 1]);
}
T query(int l, int r) {
T ans = neutr;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) ans = max(ans, st[l++]);
if (r & 1) ans = max(st[--r], ans);
}
return ans;
}
};
struct Node {
ll maxi = -INF, mini = INF, bestDiff1 = 0, bestDiff2 = 0;
};
Node merge(Node a, Node b) {
Node c;
c.maxi = max(a.maxi, b.maxi);
c.mini = min(a.mini, b.mini);
c.bestDiff1 = max({a.bestDiff1, b.bestDiff1, a.maxi - b.mini});
c.bestDiff2 = max({a.bestDiff2, b.bestDiff2, b.maxi - a.mini});
return c;
}
struct OtherSegTree {
int n;
vector<Node> st;
OtherSegTree() {}
OtherSegTree(vi &h) {
n = 1;
while (n < sz(h)) n *= 2;
st.resize(2 * n);
forn(i, sz(h)) st[i + n].maxi = st[i + n].mini = h[i];
dforsn(i, 1, n) st[i] = merge(st[2 * i], st[2 * i + 1]);
}
Node query(int l, int r) {
Node leftRes, rightRes;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) leftRes = merge(leftRes, st[l++]);
if (r & 1) rightRes = merge(st[--r], rightRes);
}
return merge(leftRes, rightRes);
}
};
int n;
vi h, val;
vi l, r;
vi Ds, roots;
PersistentSegTree persistent_segtree(0);
SegTree<ii> minH;
OtherSegTree segtree;
void init(int N, vi H) {
n = N, h = H;
l.resize(N), r.resize(N);
forn(i, N) {
int j = i - 1;
while (j >= 0 && H[j] > H[i]) j = l[j];
l[i] = j;
}
dforn(i, N) {
int j = i + 1;
while (j < N && H[j] > H[i]) j = r[j];
r[i] = j;
}
segtree = OtherSegTree(H);
vi negR(N);
vector<ii> negH(N);
forn(i, N) negH[i] = {-h[i], i};
minH = SegTree<ii>(negH, ii{-INF, -1});
vi a(N + 2, INF);
forn(i, N) a[i + 1] = H[i];
SegTree st(a, -INF);
val.resize(N);
forn(i, N) val[i] = min(st.query(l[i] + 1, i + 2), st.query(i + 1, r[i] + 2)) - H[i];
vi order(N);
iota(all(order), 0);
sort(all(order), [&](const int &lhs, const int &rhs) {
return val[lhs] > val[rhs];
});
Ds = val;
Ds.pb(INF);
sort(all(Ds));
Ds.erase(unique(all(Ds)), end(Ds));
reverse(all(Ds));
int i = 0;
int root = 0;
persistent_segtree = PersistentSegTree(n);
for (int D : Ds) {
while (i < N && val[order[i]] >= D) {
root = persistent_segtree.update(order[i++], 1, root);
}
roots.pb(root);
}
}
int max_towers(int L, int R, int D) {
int lo = 0, hi = sz(Ds);
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (D <= Ds[mid]) lo = mid;
else hi = mid;
}
int cant = persistent_segtree.query(L, R + 1, roots[lo]);
int leftmost = persistent_segtree.findFirst(L, R + 1, roots[lo]);
int rightmost = persistent_segtree.findLast(L, R + 1, roots[lo]);
if (cant == 0) {
leftmost = rightmost = minH.query(L, R + 1).snd;
assert(leftmost != -1);
cant++;
}
if (segtree.query(L, leftmost).bestDiff2 >= D) cant++;
if (segtree.query(rightmost + 1, R + 1).bestDiff1 >= D) cant++;
return cant;
}
