#include <algorithm>
#include <optional>
#include <unordered_set>
#include <vector>
#include <map>
#include <queue>
int n;
std::vector<int> h;
int max_idx;
std::map<int, int> data;
void init(int N, std::vector<int> H) {
n = N;
h = H;
max_idx = 0;
for (int i = 1; i < N; i++) {
if (H[i] > H[max_idx]) {
max_idx = i;
}
}
int towers = 0;
struct D {
int prev;
int max_to_prev;
int next;
int max_to_next;
};
std::vector<D> adj;
for (int i = 0; i < N; i++) {
towers += 1;
int max_to_prev = H[i];
int max_to_next = H[i];
if (i != 0) max_to_prev = std::max(max_to_prev, H[i - 1]);
if (i + 1 != N) max_to_next = std::max(max_to_next, H[i + 1]);
adj.push_back({.prev = i - 1,
.max_to_prev = max_to_prev,
.next = i + 1 == N ? -1 : i + 1,
.max_to_next = max_to_next});
}
struct PQItem {
int priority;
int from;
int to;
bool operator<(const PQItem &rhs) const {
return priority > rhs.priority;
}
};
std::vector<bool> active(adj.size(), true);
std::priority_queue<PQItem> pq;
for (int i = 1; i < adj.size(); i++) {
pq.push({.priority = 0, .from = i - 1, .to = i});
}
while (!pq.empty()) {
auto [priority, from, to] = pq.top();
pq.pop();
if (!active[from] || !active[to]) continue;
data.emplace(priority, towers);
if (H[from] > H[to]) {
int max = adj[to].max_to_prev =
std::max(adj[from].max_to_prev, adj[to].max_to_prev);
adj[to].prev = adj[from].prev;
if (adj[to].prev != -1) {
adj[adj[to].prev].next = to;
pq.push({.priority = max - std::max(H[adj[to].prev], H[to]),
.from = adj[to].prev,
.to = to});
}
towers -= 1;
active[from] = false;
} else {
int max = adj[from].max_to_next =
std::max(adj[from].max_to_next, adj[to].max_to_next);
adj[from].next = adj[to].next;
if (adj[from].next != -1) {
adj[adj[from].next].prev = from;
pq.push({.priority = max - std::max(H[from], H[adj[from].next]),
.from = from,
.to = adj[from].next});
}
towers -= 1;
active[to] = false;
}
}
data.emplace(2'000'000'000, towers);
}
template <typename Node>
struct SegmentTree {
std::vector<Node> nodes;
int offset;
explicit SegmentTree(int sz) : nodes(2 * sz), offset(sz) {}
void update(int idx, const Node &node) {
idx += offset;
nodes[idx] = node;
while (idx /= 2) {
nodes[idx] = nodes[2 * idx] * nodes[2 * idx + 1];
}
}
Node query(int l, int r) const {
Node left, right;
l += offset;
r += offset;
while (l < r) {
if (l & 1) left = left * nodes[l++];
if (r & 1) right = nodes[--r] * right;
l >>= 1;
r >>= 1;
}
return left * right;
}
};
int d;
struct LeftNode {
int a, b, min, max;
LeftNode() : a(-1), b(-1), min(2'000'000'000), max(-2'000'000'000) {}
LeftNode(int a) : a(-1), b(-1), min(a), max(a) {}
LeftNode(int a, int b, int min, int max) : a(a), b(b), min(min), max(max) {}
LeftNode operator*(const LeftNode &rhs) const {
std::pair<int, int> c1 = {b, a};
std::pair<int, int> c2 = {rhs.b, rhs.a};
std::pair<int, int> c3 = {-1, -1};
if (rhs.max >= 0 && rhs.max - min >= d) {
c3 = {rhs.max, min};
}
std::pair<int, int> best = std::max(std::max(c1, c2), c3);
return {best.second, best.first, std::min(min, rhs.min),
std::max(max, rhs.max)};
}
};
struct RightNode {
int a, b, min, max;
RightNode() : a(-1), b(-1), min(2'000'000'000), max(-2'000'000'000) {}
RightNode(int a) : a(-1), b(-1), min(a), max(a) {}
RightNode(int a, int b, int min, int max)
: a(a), b(b), min(min), max(max) {}
RightNode operator*(const RightNode &rhs) const {
std::pair<int, int> c1 = {b, a};
std::pair<int, int> c2 = {rhs.b, rhs.a};
std::pair<int, int> c3 = {-1, -1};
if (max >= 0 && max - rhs.min >= d) {
c3 = {max, rhs.min};
}
std::pair<int, int> best = std::max(std::max(c1, c2), c3);
return {best.second, best.first, std::min(min, rhs.min),
std::max(max, rhs.max)};
}
};
struct PrecomputedData {
std::unordered_set<int> included_s;
std::vector<int> prefix_sums, prev, next;
SegmentTree<LeftNode> left_st;
SegmentTree<RightNode> right_st;
};
std::optional<PrecomputedData> precomputed;
int max_towers(int L, int R, int D) {
if (L == R) return 1;
R += 1;
if (!precomputed) {
d = D;
std::vector<int> included{h[0]};
int intermediary = h[0];
for (int i = 1; i < n; i++) {
if (h[i] > intermediary) {
intermediary = h[i];
} else if (intermediary - included.back() < D) {
if (h[i] < included.back()) {
included.pop_back();
included.push_back(h[i]);
intermediary = h[i];
}
} else if (intermediary - h[i] >= D) {
included.push_back(h[i]);
intermediary = h[i];
}
}
std::unordered_set<int> included_s(included.begin(), included.end());
std::vector<int> prev, next;
int prev_val = -1;
for (int i = 0; i < n; i++) {
if (included_s.count(h[i])) {
prev_val = i;
}
prev.push_back(prev_val);
}
int next_val = -1;
for (int i = n - 1; i >= 0; i--) {
if (included_s.count(h[i])) {
next_val = i;
}
next.push_back(next_val);
}
std::reverse(next.begin(), next.end());
std::vector<int> prefix_sums{1};
prefix_sums.reserve(n + 1);
for (int i = 0; i < n; i++) {
prefix_sums.push_back(prefix_sums.back() + included_s.count(h[i]));
}
int o = 1;
while (o < n) o *= 2;
SegmentTree<LeftNode> left_st(o);
SegmentTree<RightNode> right_st(o);
for (int i = 0; i < n; i++) {
left_st.update(i, LeftNode(h[i]));
right_st.update(i, RightNode(h[i]));
}
precomputed = std::make_optional(PrecomputedData{
included_s, prefix_sums, prev, next, left_st, right_st});
}
if (L == 0 && R == n) {
return data.lower_bound(D)->second;
}
if (D != d) {
if (R - 1 <= max_idx) {
return 1;
}
if (L >= max_idx) {
return 1;
}
int a = h[L];
int b = h[R - 1];
int c = h[max_idx];
if (c - a >= D && c - b >= D) {
return 2;
} else {
return 1;
}
}
int total = precomputed->prefix_sums[R] - precomputed->prefix_sums[L];
int next = precomputed->next[L];
auto q0 = precomputed->left_st.query(L, next);
if (q0.b - h[next] >= D) {
total += 1;
}
int prev = precomputed->prev[R - 1];
auto q1 = precomputed->right_st.query(prev + 1, R);
if (q1.b - h[prev] >= D) {
total += 1;
}
return std::max(total, 1);
}
