#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 Fenwick{
vector<int> tree;
void init(int n) {
tree.assign(n+1, 0);
}
void upd(int i, int v, int n) {
i ++;
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
int sum(int i) {
i ++;
int ret = 0;
while
}
}*/
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 state[100010], stateS[100010];
int cand[100010];
int D;
int par[100010];
int Lpar[100010][20], Rpar[100010][20];
int Lsum[100010], Rsum[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;
if (max(lmn, rmn) > H[pv] - D) {
state[pv] = 1;
}
else cand[pv] = 1;
}
return pv;
}
void init(int _N, vector<int> _H) {
N = _N;
H = _H;
}
void dfs(int x) {
if (Lch[x] != -1) {
int y = Lch[x];
Lsum[y] = Lsum[x] + cand[x];
Rsum[y] = Rsum[x];
Lpar[y][0] = x;
Rpar[y][0] = Rpar[x][0];
dfs(y);
}
if (Rch[x] != -1) {
int y = Rch[x];
Lsum[y] = Lsum[x];
Rsum[y] = Rsum[x] + cand[x];
Lpar[y][0] = Lpar[x][0];
Rpar[y][0] = x;
dfs(y);
}
}
map<int,int> mp;
void my_init(int d) {
D = d;
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];
stateS[0] = state[0];
for (int i=1; i<N; i++) {
leafS[i] = leafS[i-1] + leaf[i];
stateS[i] = stateS[i-1] + state[i];
}
Lpar[root][0] = Rpar[root][0] = -1;
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];
}
}
}
bool flag = false;
int max_towers(int l, int r, int d) {
if (!flag) {
my_init(d);
flag = true;
}
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 = stateS[r] - (l ? stateS[l-1] : 0);
sub -= state[l] + state[r];
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 += Lsum[l] - Lsum[x];
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 += Rsum[r] - Rsum[x];
if (state[pv] == 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;
}
