#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 100005;
int N, H[mxN];
vt<int> d_vals;
struct ST {
ari2 st[mxN << 1];
void update(int i, const int v) {
st[i + N] = {v, i};
for (i += N; i >>= 1; )
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
int query(int l, int r) {
int ret = 0;
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ret = max(ret, st[l++][0]);
if (r & 1)
ret = max(ret, st[--r][0]);
}
return ret;
}
int query2(int l, int r) {
ari2 ret = {INT_MIN, -1};
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ret = max(ret, st[l++]);
if (r & 1)
ret = max(ret, st[--r]);
}
return ret[1];
}
} max_st, l_dif_st, r_dif_st, min_st;
struct Node {
int cnt, lm, rm;
Node *lft, *rht;
Node(const int c = 0, const int l = N, const int r = -1) : cnt(c), lm(l), rm(r), lft(nullptr), rht(nullptr) {}
Node(Node *l, Node *r) : cnt(l->cnt + r->cnt), lm(min(l->lm, r->lm)), rm(max(l->rm, r->rm)), lft(l), rht(r) {}
Node(Node *n) : cnt(n->cnt), lm(n->lm), rm(n->rm), lft(n->lft), rht(n->rht) {}
} *pst[mxN];
Node *build(const int tl = 0, const int tr = N - 1) {
if (tl == tr)
return new Node();
const int tm = tl + tr >> 1;
return new Node(build(tl, tm), build(tm + 1, tr));
}
Node *update(Node *n, const int p, const int tl = 0, const int tr = N - 1) {
if (tl == tr)
return new Node(1, p, p);
const int tm = tl + tr >> 1;
if (p <= tm)
return new Node(update(n->lft, p, tl, tm), n->rht);
return new Node(n->lft, update(n->rht, p, tm + 1, tr));
}
ari3 query(Node *n, const int ql, const int qr, const int tl = 0, const int tr = N - 1) {
if (tl > qr || tr < ql)
return {0, N, -1};
if (ql <= tl && tr <= qr)
return {n->cnt, n->lm, n->rm};
const int tm = tl + tr >> 1;
const ari3 l = query(n->lft, ql, qr, tl, tm), r = query(n->rht, ql, qr, tm + 1, tr);
return {l[0] + r[0], min(l[1], r[1]), max(l[2], r[2])};
}
int d_ind(const int v) { return lower_bound(all(d_vals), v) - d_vals.begin(); }
int max_towers(const int l, const int r, const int d) {
auto [ans, L, R] = query(pst[d_ind(d)], l, r);
if (R < 0)
ans = 1, L = R = min_st.query2(l, r);
return ans + (r_dif_st.query(l, L - 1) >= d) + (l_dif_st.query(R + 1, r) >= d);
}
void init(const int _N, const vt<int> _H) {
N = _N;
FOR(i, 0, N - 1)
H[i] = _H[i];
vt<int> L(N), R(N), stk;
FOR(i, 0, N - 1) {
while (size(stk) && H[stk.back()] > H[i])
stk.pop_back();
L[i] = size(stk) ? stk.back() : -1;
stk.push_back(i);
}
stk.clear();
ROF(i, N - 1, 0) {
while (size(stk) && H[stk.back()] > H[i])
stk.pop_back();
R[i] = size(stk) ? stk.back() : N;
stk.push_back(i);
}
FOR(i, 0, N - 1)
max_st.update(i, H[i]), min_st.update(i, -H[i]);
vt<int> dif(N);
FOR(i, 0, N - 1) {
const int lv = max_st.query(max(0, L[i]), i) - H[i];
const int rv = max_st.query(i, min(N - 1, R[i])) - H[i];
d_vals.push_back(dif[i] = min(lv, rv));
l_dif_st.update(i, lv);
r_dif_st.update(i, rv);
}
sort(all(d_vals));
d_vals.erase(unique(all(d_vals)), d_vals.end());
vt<vt<int>> sweep(size(d_vals));
FOR(i, 0, N - 1)
sweep[d_ind(dif[i])].push_back(i);
pst[size(d_vals)] = build();
ROF(i, size(d_vals) - 1, 0) {
pst[i] = new Node(pst[i + 1]);
for (const auto &j : sweep[i])
pst[i] = update(pst[i], j);
}
}
