#include "towers.h"
#include <algorithm>
#include <cassert>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
namespace kod {
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using std::begin;
using std::end;
using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;
template <class F> int binary_search(int ok, int ng, const F& f) {
while (std::abs(ok - ng) > 1) {
const int md = (ok + ng) / 2;
(f(md) ? ok : ng) = md;
}
return ok;
}
template <class T>
struct sparse_table {
sparse_table() = default;
explicit sparse_table(vector<T> a) {
const int n = (int)a.size();
table.push_back(std::move(a));
for (int d = 1;; ++d) {
const int m = n - (1 << d) + 1;
if (m <= 0) break;
table.emplace_back().reserve(m);
for (int i = 0; i < m; ++i) {
table[d].push_back(std::max(table[d - 1][i], table[d - 1][i + (1 << (d - 1))]));
}
}
}
T range_max(int l, int r) {
const int d = 31 - __builtin_clz(r - l);
return std::max(table[d][l], table[d][r - (1 << d)]);
}
private:
vector<vector<T>> table;
};
struct Node {
int l, r, sum;
};
vector<Node> node = {{0, 0, 0}};
int make_node(Node n) {
node.push_back(std::move(n));
return (int)node.size() - 1;
}
int make_leaf(int x) { return make_node({0, 0, x}); }
int make_parent(int l, int r) { return make_node({l, r, node[l].sum + node[r].sum}); }
int add(int u, int i, int x, int l, int r) {
if (r - l == 1) return make_leaf(x);
const int m = (l + r) / 2;
if (i < m) return make_parent(add(node[u].l, i, x, l, m), node[u].r);
return make_parent(node[u].l, add(node[u].r, i, x, m, r));
}
int fold(int u, int i, int j, int l, int r) {
if (u == 0) return 0;
if (j <= l || r <= i) return 0;
if (i <= l && r <= j) return node[u].sum;
const int m = (l + r) / 2;
return fold(node[u].l, i, j, l, m) + fold(node[u].r, i, j, m, r);
}
struct segment_tree {
struct Data {
int min, max, up, down;
};
segment_tree() = default;
explicit segment_tree(const vector<int>& H) {
size = (int)H.size();
data.resize(2 * size, {inf, -inf, -inf, -inf});
for (int i = 0; i < size; ++i) data[i + size] = {H[i], H[i], -inf, -inf};
for (int i = size - 1; i > 0; --i) data[i] = merge(data[2 * i], data[2 * i + 1]);
}
Data fold(int l, int r) const {
l += size;
r += size;
Data ret_l = {inf, -inf, -inf, -inf};
Data ret_r = {inf, -inf, -inf, -inf};
while (l < r) {
if (l & 1) ret_l = merge(ret_l, data[l++]);
if (r & 1) ret_r = merge(data[--r], ret_r);
l >>= 1;
r >>= 1;
}
return merge(ret_l, ret_r);
}
private:
int size;
vector<Data> data;
static Data merge(const Data& l, const Data& r) {
return {std::min(l.min, r.min), std::max(l.max, r.max), std::max({l.up, r.up, r.max - l.min}),
std::max({l.down, r.down, l.max - r.min})};
}
};
int N;
vector<int> H, sortedD, nodeID;
sparse_table<int> tableH, tableD;
sparse_table<pair<int, int>> minH;
segment_tree seg;
void init() {
tableH = sparse_table(H);
vector<int> D(N, inf), st;
for (int i = 0; i < N; ++i) {
while (!st.empty() && H[st.back()] >= H[i]) st.pop_back();
if (!st.empty()) {
int j = st.back();
D[i] = std::min(D[i], tableH.range_max(j, i + 1) - H[i]);
}
st.push_back(i);
}
st.clear();
for (int i = N - 1; i >= 0; --i) {
while (!st.empty() && H[st.back()] > H[i]) st.pop_back();
if (!st.empty()) {
int j = st.back();
D[i] = std::min(D[i], tableH.range_max(i, j + 1) - H[i]);
}
st.push_back(i);
}
tableD = sparse_table(D);
vector<int> ord(N);
std::iota(begin(ord), end(ord), 0);
std::sort(begin(ord), end(ord), [&](int i, int j) { return D[i] < D[j]; });
sortedD.resize(N);
nodeID.resize(N + 1);
for (int i = N - 1; i >= 0; --i) {
const int k = ord[i];
sortedD[i] = D[k];
nodeID[i] = add(nodeID[i + 1], k, 1, 0, N);
}
vector<pair<int, int>> tmp(N);
for (int i = 0; i < N; ++i) {
tmp[i] = {-H[i], i};
}
minH = sparse_table(std::move(tmp));
seg = segment_tree(H);
}
int query(int L, int R, int D) {
const int id = nodeID[std::lower_bound(begin(sortedD), end(sortedD), D) - begin(sortedD)];
int n = fold(id, L, R, 0, N);
int s = L, t = R;
if (n == 0) {
n += 1;
s = t = minH.range_max(L, R).second;
} else {
s = binary_search(R, L, [&](int k) { return tableD.range_max(L, k) >= D; }) - 1;
t = binary_search(L, R, [&](int k) { return tableD.range_max(k, R) >= D; });
}
int S = binary_search(L - 1, s, [&](int k) { return tableH.range_max(k, s) >= H[s] + D; }) + 1;
int T = binary_search(R + 1, t, [&](int k) { return tableH.range_max(t, k) >= H[t] + D; }) - 1;
// cerr << L << ' ' << S << ' ' << s << ' ' << t << ' ' << T << ' ' << R << endl;
return n + (seg.fold(L, S).up >= D) + (seg.fold(T, R).down >= D);
}
} // namespace kod
void init(int N, std::vector<int> H) {
kod::N = N;
kod::H = std::move(H);
kod::init();
}
int max_towers(int L, int R, int D) { return kod::query(L, R + 1, D); }
