#include "towers.h"
#include <bits/stdc++.h>
namespace std {
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
namespace ecnerwala {
namespace seg_tree {
// Floor of log_2(a); index of highest 1-bit
inline int log_2(int a) {
return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
}
inline int next_pow_2(int a) {
assert(a > 0);
return 1 << log_2(2*a-1);
}
struct point {
int a;
point() : a(0) {}
explicit point(int a_) : a(a_) { assert(a >= -1); }
explicit operator bool () { return bool(a); }
// This is useful so you can directly do array indices
/* implicit */ operator int() const { return a; }
point c(bool z) const {
return point((a<<1)|z);
}
point operator [] (bool z) const {
return c(z);
}
point p() const {
return point(a>>1);
}
friend std::ostream& operator << (std::ostream& o, const point& p) { return o << int(p); }
template <typename F> void for_each(F f) const {
for (int v = a; v > 0; v >>= 1) {
f(point(v));
}
}
template <typename F> void for_parents_down(F f) const {
// strictly greater than 0
for (int L = log_2(a); L > 0; L--) {
f(point(a >> L));
}
}
template <typename F> void for_parents_up(F f) const {
for (int v = a >> 1; v > 0; v >>= 1) {
f(point(v));
}
}
point& operator ++ () { ++a; return *this; }
point operator ++ (int) { return point(a++); }
point& operator -- () { --a; return *this; }
point operator -- (int) { return point(a--); }
};
struct range {
int a, b;
range() : a(1), b(1) {}
range(int a_, int b_) : a(a_), b(b_) {
assert(1 <= a && a <= b && b <= 2 * a);
}
explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}
explicit operator std::array<int, 2>() const {
return {a,b};
}
const int& operator[] (bool z) const {
return z ? b : a;
}
friend std::ostream& operator << (std::ostream& o, const range& r) { return o << "[" << r.a << ".." << r.b << ")"; }
// Iterate over the range from outside-in.
// Calls f(point a)
template <typename F> void for_each(F f) const {
for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
if (x & 1) f(point(x++));
if (y & 1) f(point(--y));
}
}
// Iterate over the range from outside-in.
// Calls f(point a, bool is_right)
template <typename F> void for_each_with_side(F f) const {
for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
if (x & 1) f(point(x++), false);
if (y & 1) f(point(--y), true);
}
}
// Iterate over the range from left to right.
// Calls f(point)
template <typename F> void for_each_l_to_r(F f) const {
int anc_depth = log_2((a-1) ^ b);
int anc_msk = (1 << anc_depth) - 1;
for (int v = (-a) & anc_msk; v; v &= v-1) {
int i = __builtin_ctz(v);
f(point(((a-1) >> i) + 1));
}
for (int v = b & anc_msk; v; ) {
int i = log_2(v);
f(point((b >> i) - 1));
v ^= (1 << i);
}
}
// Iterate over the range from right to left.
// Calls f(point)
template <typename F> void for_each_r_to_l(F f) const {
int anc_depth = log_2((a-1) ^ b);
int anc_msk = (1 << anc_depth) - 1;
for (int v = b & anc_msk; v; v &= v-1) {
int i = __builtin_ctz(v);
f(point((b >> i) - 1));
}
for (int v = (-a) & anc_msk; v; ) {
int i = log_2(v);
f(point(((a-1) >> i) + 1));
v ^= (1 << i);
}
}
template <typename F> void for_parents_down(F f) const {
int x = a, y = b;
if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
int dx = __builtin_ctz(x);
int dy = __builtin_ctz(y);
int anc_depth = log_2((x-1) ^ y);
for (int i = log_2(x); i > dx; i--) {
f(point(x >> i));
}
for (int i = anc_depth; i > dy; i--) {
f(point(y >> i));
}
}
template <typename F> void for_parents_up(F f) const {
int x = a, y = b;
if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
int dx = __builtin_ctz(x);
int dy = __builtin_ctz(y);
int anc_depth = log_2((x-1) ^ y);
for (int i = dx+1; i <= anc_depth; i++) {
f(point(x >> i));
}
for (int v = y >> (dy+1); v; v >>= 1) {
f(point(v));
}
}
};
struct in_order_layout {
// Alias them in for convenience
using point = seg_tree::point;
using range = seg_tree::range;
int N, S;
in_order_layout() : N(0), S(0) {}
in_order_layout(int N_) : N(N_), S(N ? next_pow_2(N) : 0) {}
point get_point(int a) const {
assert(0 <= a && a < N);
a += S;
return point(a >= 2 * N ? a - N : a);
}
range get_range(int a, int b) const {
assert(0 <= a && a <= b && b <= N);
if (N == 0) return range();
a += S, b += S;
return range((a >= 2 * N ? 2*(a-N) : a), (b >= 2 * N ? 2*(b-N) : b));
}
range get_range(std::array<int, 2> p) const {
return get_range(p[0], p[1]);
}
int get_leaf_index(point pt) const {
int a = int(pt);
assert(N <= a && a < 2 * N);
return (a < S ? a + N : a) - S;
}
std::array<int, 2> get_node_bounds(point pt) const {
int a = int(pt);
assert(1 <= a && a < 2 * N);
int l = __builtin_clz(a) - __builtin_clz(2*N-1);
int x = a << l, y = (a+1) << l;
assert(S <= x && x < y && y <= 2*S);
return {(x >= 2 * N ? (x>>1) + N : x) - S, (y >= 2 * N ? (y>>1) + N : y) - S};
}
int get_node_split(point pt) const {
int a = int(pt);
assert(1 <= a && a < N);
int l = __builtin_clz(2*a+1) - __builtin_clz(2*N-1);
int x = (2*a+1) << l;
assert(S <= x && x < 2*S);
return (x >= 2 * N ? (x>>1) + N : x) - S;
}
int get_node_size(point pt) const {
auto bounds = get_node_bounds(pt);
return bounds[1] - bounds[0];
}
};
struct circular_layout {
// Alias them in for convenience
using point = seg_tree::point;
using range = seg_tree::range;
int N;
circular_layout() : N(0) {}
circular_layout(int N_) : N(N_) {}
point get_point(int a) const {
assert(0 <= a && a < N);
return point(N + a);
}
range get_range(int a, int b) const {
assert(0 <= a && a <= b && b <= N);
if (N == 0) return range();
return range(N + a, N + b);
}
range get_range(std::array<int, 2> p) const {
return get_range(p[0], p[1]);
}
int get_leaf_index(point pt) const {
int a = int(pt);
assert(N <= a && a < 2 * N);
return a - N;
}
// Returns {x,y} so that 0 <= x < N and 1 <= y <= N
// If the point is non-wrapping, then 0 <= x < y <= N
std::array<int, 2> get_node_bounds(point pt) const {
int a = int(pt);
assert(1 <= a && a < 2 * N);
int l = __builtin_clz(a) - __builtin_clz(2*N-1);
int S = next_pow_2(N);
int x = a << l, y = (a+1) << l;
assert(S <= x && x < y && y <= 2*S);
return {(x >= 2 * N ? x >> 1 : x) - N, (y > 2 * N ? y >> 1 : y) - N};
}
// Returns the split point of the node, such that 1 <= s <= N.
int get_node_split(point pt) const {
int a = int(pt);
assert(1 <= a && a < N);
return get_node_bounds(pt.c(0))[1];
}
int get_node_size(point pt) const {
auto bounds = get_node_bounds(pt);
int r = bounds[1] - bounds[0];
return r > 0 ? r : r + N;
}
};
} // namespace seg_tree
template <typename T, class Compare = std::less<T>> class RangeMinQuery : private Compare {
static const int BUCKET_SIZE = 32;
static const int BUCKET_SIZE_LOG = 5;
static_assert(BUCKET_SIZE == (1 << BUCKET_SIZE_LOG), "BUCKET_SIZE should be a power of 2");
static const int CACHE_LINE_ALIGNMENT = 64;
int n = 0;
std::vector<T> data;
std::vector<T> pref_data;
std::vector<T> suff_data;
std::vector<T> sparse_table;
std::vector<uint32_t> range_mask;
private:
int num_buckets() const {
return n >> BUCKET_SIZE_LOG;
}
int num_levels() const {
return num_buckets() ? 32 - __builtin_clz(num_buckets()) : 0;
}
int sparse_table_size() const {
return num_buckets() * num_levels();
}
private:
const T& min(const T& a, const T& b) const {
return Compare::operator()(a, b) ? a : b;
}
void setmin(T& a, const T& b) const {
if (Compare::operator()(b, a)) a = b;
}
template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
public:
RangeMinQuery() {}
template <typename Vec> explicit RangeMinQuery(const Vec& data_, const Compare& comp_ = Compare())
: Compare(comp_)
, n(get_size(data_))
, data(n)
, pref_data(n)
, suff_data(n)
, sparse_table(sparse_table_size())
, range_mask(n)
{
for (int i = 0; i < n; i++) data[i] = data_[i];
for (int i = 0; i < n; i++) {
if (i & (BUCKET_SIZE-1)) {
uint32_t m = range_mask[i-1];
while (m && !Compare::operator()(data[(i | (BUCKET_SIZE-1)) - __builtin_clz(m)], data[i])) {
m -= uint32_t(1) << (BUCKET_SIZE - 1 - __builtin_clz(m));
}
m |= uint32_t(1) << (i & (BUCKET_SIZE - 1));
range_mask[i] = m;
} else {
range_mask[i] = 1;
}
}
for (int i = 0; i < n; i++) {
pref_data[i] = data[i];
if (i & (BUCKET_SIZE-1)) {
setmin(pref_data[i], pref_data[i-1]);
}
}
for (int i = n-1; i >= 0; i--) {
suff_data[i] = data[i];
if (i+1 < n && ((i+1) & (BUCKET_SIZE-1))) {
setmin(suff_data[i], suff_data[i+1]);
}
}
for (int i = 0; i < num_buckets(); i++) {
sparse_table[i] = data[i * BUCKET_SIZE];
for (int v = 1; v < BUCKET_SIZE; v++) {
setmin(sparse_table[i], data[i * BUCKET_SIZE + v]);
}
}
for (int l = 0; l+1 < num_levels(); l++) {
for (int i = 0; i + (1 << (l+1)) <= num_buckets(); i++) {
sparse_table[(l+1) * num_buckets() + i] = min(sparse_table[l * num_buckets() + i], sparse_table[l * num_buckets() + i + (1 << l)]);
}
}
}
T query(int l, int r) const {
assert(l <= r);
int bucket_l = (l >> BUCKET_SIZE_LOG);
int bucket_r = (r >> BUCKET_SIZE_LOG);
if (bucket_l == bucket_r) {
uint32_t msk = range_mask[r] & ~((uint32_t(1) << (l & (BUCKET_SIZE-1))) - 1);
int ind = (l & ~(BUCKET_SIZE-1)) + __builtin_ctz(msk);
return data[ind];
} else {
T ans = min(suff_data[l], pref_data[r]);
bucket_l++;
if (bucket_l < bucket_r) {
int level = (32 - __builtin_clz(bucket_r - bucket_l)) - 1;
setmin(ans, sparse_table[level * num_buckets() + bucket_l]);
setmin(ans, sparse_table[level * num_buckets() + bucket_r - (1 << level)]);
}
return ans;
}
}
};
template <typename T> using RangeMaxQuery = RangeMinQuery<T, std::greater<T>>;
struct TowersSolver {
int N;
std::vector<int> H;
std::vector<int> peak_height;
std::vector<std::vector<int>> seg_cnt;
seg_tree::in_order_layout layout;
RangeMinQuery<int> rmq;
TowersSolver() {}
TowersSolver(std::vector<int> H_) : N(int(H_.size())), H(H_), peak_height(N), seg_cnt(N), layout(N), rmq(H) {
{
struct stk_t {
int h;
int idx;
int l_lo;
int r_lo;
};
std::vector<stk_t> stk; stk.reserve(N);
for (int i = 0; i <= N; i++) {
int h = i == N ? (*std::max_element(H.begin(), H.end())) + 1 : H[i];
int cur_lo = h;
while (!stk.empty() && h > stk.back().h) {
stk.back().r_lo = std::min(stk.back().r_lo, cur_lo);
peak_height[stk.back().idx] = stk.back().h - std::max(stk.back().l_lo, stk.back().r_lo);
cur_lo = std::min(stk.back().l_lo, stk.back().r_lo);
stk.pop_back();
}
stk.push_back(stk_t{h, i, cur_lo, h});
}
}
{
std::vector<int> buf; buf.reserve(N);
for (seg_tree::point a(N-1); a > 0; a--) {
auto [l, r] = layout.get_node_bounds(a);
int m = layout.get_node_split(a);
seg_cnt[a].reserve(r-l+1);
seg_cnt[a].push_back(0);
for (int i = 0, j = 0; i < m-l || j < r-m; ) {
if (i < m-l && (j == r-m || peak_height[l+i] >= peak_height[m+j])) {
buf.push_back(peak_height[l+i]);
i++;
} else {
buf.push_back(peak_height[m+j]);
j++;
}
seg_cnt[a].push_back(j);
}
std::copy(buf.begin(), buf.end(), peak_height.begin() + l);
buf.clear();
}
}
}
int max_towers(int L, int R, int D) {
assert(0 <= L && L < R && R <= N);
// Custom lower bound cause reversed
int root_cnt = [&]() -> int {
int mi = -1, ma = N;
while (ma - mi > 1) {
int md = mi + ((ma - mi) >> 1);
if (peak_height[md] >= D) mi = md;
else ma = md;
}
return ma;
}();
int cnt_hi = 0;
seg_tree::point l_pos(0); int l_cnt = -1;
seg_tree::point r_pos(0); int r_cnt = -1;
std::y_combinator([&](auto self, seg_tree::point a, int cnt) -> void {
if (cnt == 0) return;
assert(cnt > 0);
auto [l, r] = layout.get_node_bounds(a);
if (r <= L || R <= l) return;
if (L <= l && r <= R) {
cnt_hi += cnt;
if (l_pos == 0) {
l_pos = a, l_cnt = cnt;
}
r_pos = a, r_cnt = cnt;
return;
}
int v = seg_cnt[a][cnt];
self(a.c(0), cnt - v);
self(a.c(1), v);
})(seg_tree::point(1), root_cnt);
if (cnt_hi == 0) return 1;
assert(l_cnt != -1 && r_cnt != -1);
while (l_pos < N) {
int v = seg_cnt[l_pos][l_cnt];
if (l_cnt - v > 0) {
l_pos = l_pos.c(0);
l_cnt = l_cnt - v;
} else {
l_pos = l_pos.c(1);
l_cnt = v;
}
}
int l_idx = layout.get_leaf_index(l_pos);
if (H[l_idx] - rmq.query(L, l_idx) < D) {
cnt_hi--;
}
if (cnt_hi == 0) return 1;
while (r_pos < N) {
int v = seg_cnt[r_pos][r_cnt];
if (v > 0) {
r_pos = r_pos.c(1);
r_cnt = v;
} else {
r_pos = r_pos.c(0);
r_cnt = r_cnt - v;
}
}
int r_idx = layout.get_leaf_index(r_pos);
if (H[r_idx] - rmq.query(r_idx, R - 1) < D) {
cnt_hi--;
}
return 1 + cnt_hi;
}
};
static TowersSolver solver;
}
void init(int N, std::vector<int> H) {
assert(N == int(H.size()));
ecnerwala::solver = ecnerwala::TowersSolver(H);
}
int max_towers(int L, int R, int D) {
return ecnerwala::solver.max_towers(L, R+1, D);
}
