#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T, size_t L>
struct max_segtree
{
T t[L << 1];
max_segtree() { fill(t, t + (L << 1), numeric_limits<T>::min() / 4); }
void update(size_t i, T x)
{
i += L;
t[i] = max(t[i], x);
while (i >>= 1)
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
T range_max(size_t i, size_t j)
{
i += L, j += L;
T x = numeric_limits<T>::min() / 4;
while (i <= j)
{
if (i & 1)
x = max(x, t[i++]);
if (!(j & 1))
x = max(x, t[j--]);
i >>= 1;
j >>= 1;
}
return x;
}
};
template <typename T, size_t L>
struct min_segtree
{
T t[L << 1];
min_segtree() { fill(t, t + (L << 1), numeric_limits<T>::max() / 4); }
void update(size_t i, T x)
{
i += L;
t[i] = min(t[i], x);
while (i >>= 1)
t[i] = min(t[i << 1], t[i << 1 | 1]);
}
T range_min(size_t i, size_t j)
{
i += L, j += L;
T x = numeric_limits<T>::max() / 4;
while (i <= j)
{
if (i & 1)
x = min(x, t[i++]);
if (!(j & 1))
x = min(x, t[j--]);
i >>= 1;
j >>= 1;
}
return x;
}
size_t min_index_r(size_t i, size_t j, T x, size_t k = 1, size_t a = 0, size_t b = L - 1)
{
if (b < i || a > j)
return SIZE_MAX;
if (i <= a && b <= j)
{
if (t[k] != x)
return SIZE_MAX;
while (a != b)
{
if (t[k << 1] == x)
k = k << 1, b = (a + b) >> 1;
else
k = k << 1 | 1, a = ((a + b) >> 1) + 1;
}
return a;
}
size_t y = min_index_r(i, j, x, k << 1, a, (a + b) >> 1);
if (y != SIZE_MAX)
return y;
return min_index_r(i, j, k << 1 | 1, ((a + b) >> 1) + 1, b);
}
size_t min_index(size_t i, size_t j)
{
return min_index_r(i, j, range_min(i, j));
}
};
template <typename T, size_t L>
struct left_diff_segtree
{
struct node
{
T diff, max_val, min_val;
node() { diff = numeric_limits<T>::min() / 4, max_val = numeric_limits<T>::min() / 4, min_val = numeric_limits<T>::max() / 4; }
node(T diff, T max_val, T min_val) { this->diff = diff, this->max_val = max_val, this->min_val = min_val; }
};
node t[L << 1];
node combine(node a, node b)
{
return node(max(a.diff, max(b.diff, b.max_val - a.min_val)),
max(a.max_val, b.max_val),
min(a.min_val, b.min_val));
}
void update(size_t i, T x)
{
i += L;
t[i].diff = 0;
t[i].min_val = t[i].max_val = x;
while (i >>= 1)
t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
T max_diff(size_t i, size_t j)
{
i += L, j += L;
node x(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4),
y(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4);
while (i <= j)
{
if (i & 1)
x = combine(x, t[i++]);
if (!(j & 1))
y = combine(t[j--], y);
i >>= 1;
j >>= 1;
}
return combine(x, y).diff;
}
};
template <typename T, size_t L>
struct right_diff_segtree
{
struct node
{
T diff, max_val, min_val;
node() { diff = numeric_limits<T>::min() / 4, max_val = numeric_limits<T>::min() / 4, min_val = numeric_limits<T>::max() / 4; }
node(T diff, T max_val, T min_val) { this->diff = diff, this->max_val = max_val, this->min_val = min_val; }
};
node t[L << 1];
node combine(node a, node b)
{
return node(max(a.diff, max(b.diff, a.max_val - b.min_val)),
max(a.max_val, b.max_val),
min(a.min_val, b.min_val));
}
void update(size_t i, T x)
{
i += L;
t[i].diff = 0;
t[i].min_val = t[i].max_val = x;
while (i >>= 1)
t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
T max_diff(size_t i, size_t j)
{
i += L, j += L;
node x(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4),
y(numeric_limits<T>::min() / 4, numeric_limits<T>::min() / 4, numeric_limits<T>::max() / 4);
while (i <= j)
{
if (i & 1)
x = combine(x, t[i++]);
if (!(j & 1))
y = combine(t[j--], y);
i >>= 1;
j >>= 1;
}
return combine(x, y).diff;
}
};
struct node
{
uint32_t l, r, s;
};
constexpr size_t N = 100000, M = 4000000, L = 1 << 17;
node tree[M];
uint32_t roots[N];
vector<int64_t> delta_coords;
size_t n, left_greater[N], left_smaller[N], right_greater[N], right_smaller[N], num_nodes;
int64_t h[N];
max_segtree<int64_t, L> hmax;
min_segtree<int64_t, L> hmin;
left_diff_segtree<int64_t, L> ltree;
right_diff_segtree<int64_t, L> rtree;
uint32_t incr(size_t i, uint32_t x, size_t k, size_t a = 0, size_t b = L - 1)
{
uint32_t new_node = num_nodes++;
if (a == b)
{
tree[new_node].s = tree[k].s + x;
return new_node;
}
if (i <= (a + b) >> 1)
{
tree[new_node].r = tree[k].r;
tree[new_node].l = incr(i, x, tree[k].l, a, (a + b) >> 1);
}
else
{
tree[new_node].l = tree[k].l;
tree[new_node].r = incr(i, x, tree[k].r, ((a + b) >> 1) + 1, b);
}
tree[new_node].s = tree[tree[new_node].l].s + tree[tree[new_node].r].s;
return new_node;
}
uint32_t range_sum(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
if (b < i || a > j)
return 0;
if (i <= a && b <= j)
return tree[k].s;
return range_sum(i, j, tree[k].l, a, (a + b) >> 1) +
range_sum(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
}
size_t leftmost_nonzero(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
if (b < i || a > j)
return SIZE_MAX;
if (i <= a && b <= j)
{
if (!tree[k].s)
return SIZE_MAX;
while (a != b)
{
if (tree[tree[k].l].s)
k = tree[k].l, b = (a + b) >> 1;
else
k = tree[k].r, a = ((a + b) >> 1) + 1;
}
return a;
}
size_t y = leftmost_nonzero(i, j, tree[k].l, a, (a + b) >> 1);
if (y != SIZE_MAX)
return y;
return leftmost_nonzero(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
}
size_t rightmost_nonzero(size_t i, size_t j, size_t k, size_t a = 0, size_t b = L - 1)
{
if (b < i || a > j)
return SIZE_MAX;
if (i <= a && b <= j)
{
if (!tree[k].s)
return SIZE_MAX;
while (a != b)
{
if (tree[tree[k].r].s)
k = tree[k].r, a = ((a + b) >> 1) + 1;
else
k = tree[k].l, b = (a + b) >> 1;
}
return a;
}
size_t y = rightmost_nonzero(i, j, tree[k].r, ((a + b) >> 1) + 1, b);
if (y != SIZE_MAX)
return y;
return rightmost_nonzero(i, j, tree[k].l, a, (a + b) >> 1);
}
uint32_t get_root(int64_t delta)
{
return roots[upper_bound(delta_coords.begin(), delta_coords.end(), delta, greater<int64_t>()) - delta_coords.begin() - 1];
}
void init(int n_, vector<int> h_)
{
n = n_;
for (size_t i = 0; i < n; ++i)
h[i] = h_[i];
{
stack<size_t> s;
for (size_t i = 0; i < n; ++i)
{
while (!s.empty() && h[s.top()] < h[i])
s.pop();
left_greater[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = 0; i < n; ++i)
{
while (!s.empty() && h[s.top()] > h[i])
s.pop();
left_smaller[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = n - 1; i < n; --i)
{
while (!s.empty() && h[s.top()] < h[i])
s.pop();
right_greater[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = n - 1; i < n; --i)
{
while (!s.empty() && h[s.top()] > h[i])
s.pop();
right_smaller[i] = !s.empty() ? s.top() : SIZE_MAX;
s.push(i);
}
}
for (size_t i = 0; i < n; ++i)
{
hmax.update(i, h[i]), hmin.update(i, h[i]);
ltree.update(i, h[i]);
rtree.update(i, h[i]);
}
vector<pair<int64_t, size_t>> delta;
for (size_t i = 0; i < n; ++i)
{
int64_t d = INT64_MAX;
if (left_smaller[i] != SIZE_MAX)
d = min(d, hmax.range_max(left_smaller[i] + 1, i - 1));
if (right_smaller[i] != SIZE_MAX)
d = min(d, hmax.range_max(i + 1, right_smaller[i] - 1));
if (left_smaller[i] == SIZE_MAX && right_smaller[i] == SIZE_MAX)
delta.emplace_back(INT64_MAX, i);
else if (d != INT64_MIN)
delta.emplace_back((d - h[i]), i);
}
sort(delta.begin(), delta.end(), greater<pair<int64_t, size_t>>());
uint32_t curr_root = 1;
for (size_t i = L - 1; i; --i)
tree[i].l = i << 1, tree[i].r = i << 1 | 1;
num_nodes = L << 1;
for (size_t i = 0, k = 0; i < delta.size();)
{
size_t j = i;
while (j < delta.size() && delta[j].first == delta[i].first)
curr_root = incr(delta[j].second, 1, curr_root), ++j;
roots[k] = curr_root;
delta_coords.push_back(delta[i].first);
i = j;
++k;
}
}
int max_towers(int l, int r, int d)
{
uint32_t rt = get_root(d);
uint32_t y = range_sum(l, r, rt);
if (!y)
{
size_t smallest = hmin.min_index(l, r);
return 1 + ((smallest != l && ltree.max_diff(l, smallest - 1) >= d) ||
(smallest != r && rtree.max_diff(smallest + 1, r) >= d));
}
else
{
size_t u = leftmost_nonzero(l, r, rt),
v = rightmost_nonzero(l, r, rt);
return y + (u != l && ltree.max_diff(l, u - 1) >= d) +
(v != r && rtree.max_diff(v + 1, r) >= d);
}
}
