#include "towers.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct SegmentTree{
vector<pair<int,int>> tree;
void init(int n, vector<int> a) {
int sz = 1 << __lg(n) + 2;
tree.resize(sz);
build(1, 0, n-1, a);
}
void build(int node, int s, int e, vector<int> &a) {
if (s == e) {
tree[node] = {a[s], s};
return;
}
int mid = s + e >> 1;
build(node*2, s, mid, a);
build(node*2+1, mid+1, e, a);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
pair<int,int> query(int node, int s, int e, int l, int r) {
if (l > e || s > r) return {-inf, -1};
if (l <= s && e <= r) return tree[node];
int mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
struct Node{
int l, r, val;
};
struct PersistentSegmentTree{
vector<Node> tree;
void init() {
tree.clear();
tree.push_back({-1, -1, 0});
}
void update(int pnode, int node, int s, int e, int tar, int val) {
tree[node].val = val;
if (pnode != -1) tree[node].val += tree[pnode].val;
if (s == e) {
return;
}
int mid = s + e >> 1;
if (tar <= mid) {
tree[node].l = tree.size();
tree.push_back({-1, -1, 0});
if (pnode != -1) tree[node].r = tree[pnode].r;
update((pnode == -1 ? -1 : tree[pnode].l), tree[node].l, s, mid, tar, val);
}
else {
tree[node].r = tree.size();
tree.push_back({-1, -1, 0});
if (pnode != -1) tree[node].l = tree[pnode].l;
update((pnode == -1 ? -1 : tree[pnode].r), tree[node].r, mid+1, e, tar, val);
}
}
int query(int node, int s, int e, int l, int r) {
if (node == -1 || l > e || s > r) return 0;
if (l <= s && e <= r) return tree[node].val;
int mid = s + e >> 1;
return query(tree[node].l, s, mid, l, r) + query(tree[node].r, mid+1, e, l, r);
}
int newroot() {
tree.push_back({-1, -1, 0});
return tree.size() - 1;
}
};
SegmentTree seg, minseg;
int Lch[100010], Rch[100010], L[100010], R[100010];
vector<int> H;
int N;
int root;
int leaf[100010], leafS[100010];
int cand[100010];
int D;
int par[100010];
int Lpar[100010][20], Rpar[100010][20];
int diff[100010];
PersistentSegmentTree PST, PSTL, PSTR;
int head[100010], headL[100010], headR[100010];
int makeTree(int l, int r) {
if (l > r) return -1;
pair<int,int> ret = seg.query(1, 0, N-1, l, r);
int pv = ret.second;
L[pv] = l; R[pv] = r;
Lch[pv] = makeTree(l, pv-1);
Rch[pv] = makeTree(pv+1, r);
if (Lch[pv] != -1) par[Lch[pv]] = pv;
if (Rch[pv] != -1) par[Rch[pv]] = pv;
if (Lch[pv] == -1 && Rch[pv] == -1) {
leaf[pv] = 1;
}
else if (Lch[pv] != -1 && Rch[pv] != -1) {
int lmn = -minseg.query(1, 0, N-1, l, pv-1).first;
int rmn = -minseg.query(1, 0, N-1, pv+1, r).first;
diff[pv] = H[pv] - max(lmn, rmn);
}
return pv;
}
void dfs(int x) {
if (Lch[x] != -1) {
int y = Lch[x];
if (Lch[x] != -1 && Rch[x] != -1) {
headL[y] = PSTL.newroot();
PSTL.update(headL[x], headL[y], 0, inf, diff[x], 1);
}
else {
headL[y] = headL[x];
}
headR[y] = headR[x];
Lpar[y][0] = x;
Rpar[y][0] = Rpar[x][0];
dfs(y);
}
if (Rch[x] != -1) {
int y = Rch[x];
headL[y] = headL[x];
if (Lch[x] != -1 && Rch[x] != -1) {
headR[y] = PSTR.newroot();
PSTR.update(headR[x], headR[y], 0, inf, diff[x], 1);
}
else {
headR[y] = headR[x];
}
Lpar[y][0] = Lpar[x][0];
Rpar[y][0] = x;
dfs(y);
}
}
void init(int _N, vector<int> _H) {
N = _N;
H = _H;
seg.init(N, H);
vector<int> t = H;
for (auto &x : t) x = -x;
minseg.init(N, t);
root = makeTree(0, N-1);
par[root] = -1;
leafS[0] = leaf[0];
for (int i=1; i<N; i++) {
leafS[i] = leafS[i-1] + leaf[i];
}
PST.init();
int prv = 0;
for (int i=0; i<N; i++) {
if (Lch[i] != -1 && Rch[i] != -1) {
head[i] = PST.newroot();
PST.update(prv, head[i], 0, inf, diff[i], 1);
}
else {
head[i] = prv;
}
prv = head[i];
}
Lpar[root][0] = Rpar[root][0] = -1;
PSTL.init();
PSTR.init();
headL[root] = headR[root] = 0;
dfs(root);
for (int lv=1; lv<=19; lv++) {
for (int i=0; i<N; i++) {
if (Lpar[i][lv-1] == -1) Lpar[i][lv] = -1;
else Lpar[i][lv] = Lpar[Lpar[i][lv-1]][lv-1];
if (Rpar[i][lv-1] == -1) Rpar[i][lv] = -1;
else Rpar[i][lv] = Rpar[Rpar[i][lv-1]][lv-1];
}
}
}
int state(int i, int d) {
return Lch[i] != -1 && Rch[i] != -1 && diff[i] < d;
}
int max_towers(int l, int r, int d) {
if (l == r) return 1;
int ans = leafS[r] - (l ? leafS[l-1] : 0);
if (!leaf[l] && Rch[l] == -1) ans ++;
if (!leaf[r] && Lch[r] == -1) ans ++;
int sub = PST.query(head[r], 0, inf, 0, d-1) - (l ? PST.query(head[l-1], 0, inf, 0, d-1) : 0);
sub -= state(l, d) + state(r, d);
pair<int,int> ret = seg.query(1, 0, N-1, l, r);
int mx = ret.first, pv = ret.second;
int x = l;
for (int lv=19; lv>=0; lv--) {
if (Lpar[x][lv] != -1 && H[Lpar[x][lv]] < mx) {
int p = Lpar[x][lv];
int mn = -minseg.query(1, 0, N-1, l, p-1).first;
if (mn > H[p] - d) x = p;
}
}
sub += PSTL.query(headL[l], 0, inf, d, inf) - PSTL.query(headL[x], 0, inf, d, inf);
x = r;
for (int lv=19; lv>=0; lv--) {
if (Rpar[x][lv] != -1 && H[Rpar[x][lv]] < mx) {
int p = Rpar[x][lv];
int mn = -minseg.query(1, 0, N-1, p+1, r).first;
if (mn > H[p] - d) x = p;
}
}
sub += PSTR.query(headR[r], 0, inf, d, inf) - PSTR.query(headR[x], 0, inf, d, inf);
if (state(pv, d) == 0 && l != pv && r != pv) {
int mnL = -minseg.query(1, 0, N-1, l, pv-1).first;
int mnR = -minseg.query(1, 0, N-1, pv+1, r).first;
if (max(mnL, mnR) > mx - d) sub ++;
}
return ans - sub;
}
