#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9 + 5;
struct MaxSeg {
int seg[1 << 18];
MaxSeg() {
fill(seg, seg + (1 << 18), -inf);
}
void update(int i, int s, int e, int x, int v) {
if (s == e) {
seg[i] = v;
return;
}
int m = (s + e) / 2;
if (x <= m) update(i + i, s, m, x, v);
else update(i + i + 1, m + 1, e, x, v);
seg[i] = max(seg[i + i], seg[i + i + 1]);
}
int query(int i, int s, int e, int x, int y) const {
if (e < x || y < s) return -inf;
if (x <= s && e <= y) return seg[i];
int m = (s + e) / 2;
return max(query(i + i, s, m, x, y), query(i + i + 1, m + 1, e, x, y));
}
int find(int i, int s, int e, int x, int v) const {
if (x < s) return 0;
if (e <= x && seg[i] <= v) return 0;
if (s == e) return s;
int m = (s + e) / 2;
int r = find(i + i + 1, m + 1, e, x, v);
if (r) return r;
return find(i + i, s, m, x, v);
}
};
struct Pst {
struct Node {
int L, R, S;
};
int root;
vector<Node> node;
vector<int> snapshots;
Pst() {
root = 0;
node.push_back(Node { 0, 0, 0 });
snapshots.push_back(0);
}
int update(int i, int s, int e, int x, int v) {
int j = node.size();
node.push_back(node[i]);
node[j].S += v;
if (s < e) {
int m = (s + e) / 2;
if (x <= m) node[j].L = update(node[j].L, s, m, x, v);
else node[j].R = update(node[j].R, m + 1, e, x, v);
}
return j;
}
void update(int x, int v) {
if (x == 0) return;
root = update(root, 1, inf, x, v);
}
int query(int i, int s, int e, int x, int y) const {
if (!i || e < x || y < s) return 0;
if (x <= s && e <= y) return node[i].S;
int m = (s + e) / 2;
return query(node[i].L, s, m, x, y) + query(node[i].R, m + 1, e, x, y);
}
int query(int t, int x, int y) const {
return query(snapshots[t], 1, inf, x, y);
}
void snapshot() {
snapshots.push_back(root);
}
};
int n;
struct Tower {
MaxSeg min_seg, max_seg;
int maxD[100005];
int Lmin[100005];
int Lpos[100005];
int Lpar[20][100005];
int Ldep[100005];
int V[100005];
Pst pst;
void init(vector<int> H) {
H.insert(H.begin(), inf);
for (int i = 1; i <= n; ++i) {
V[i] = H[i];
min_seg.update(1, 1, n, i, -H[i]);
max_seg.update(1, 1, n, i, H[i]);
}
vector<int> R = { 0, 1 };
vector<int> L = { 0 };
pst.snapshot();
Lmin[0] = Lmin[1] = inf;
for (int i = 2; i <= n; ++i) {
int poped = 0;
Lmin[i] = inf;
while (H[R.back()] < H[i]) {
Lmin[i] = min(Lmin[i], min(Lmin[R.back()], H[R.back()]));
if (L.back() == R.back()) L.pop_back();
R.pop_back();
++poped;
}
if (!poped) {
while (L.back()) {
int x = L.back();
pst.update(maxD[x], -1);
if (Lmin[x] < H[i]) {
maxD[x] = H[x] - H[i];
pst.update(maxD[x], 1);
break;
}
else {
maxD[x] = H[x] - Lmin[x];
pst.update(maxD[x], 1);
L.pop_back();
}
}
}
else {
Lpar[0][i] = L.back();
Ldep[i] = Ldep[Lpar[0][i]] + 1;
L.push_back(i);
}
Lpos[i] = L.empty() ? 0 : L.back();
R.push_back(i);
pst.snapshot();
}
for (int i = 1; i < 20; ++i) {
for (int j = 1; j <= n; ++j) Lpar[i][j] = Lpar[i - 1][Lpar[i - 1][j]];
}
}
int query(int m, int r, int d) const {
// printf("m = %d, r = %d\n", m, r);
if (m == r) return 0;
int ans = pst.query(r, d, inf) - pst.query(m, d, inf);
int mn = -min_seg.query(1, 1, n, m + 1, r);
int x = Lpos[m];
if (!x) return ans;
int p = Lpar[0][x];
if (Lmin[x] + d <= V[x] && mn + d <= V[x]);
else if (p && Lmin[p] + d <= V[p] && min(mn, Lmin[x]) + d <= V[p]) x = p;
else {
for (int i = 20; i--; ) {
int p = Lpar[i][x];
int g = Lpar[0][p];
if (!g) continue;
if (Lmin[g] + d <= V[g] && min(mn, Lmin[p]) + d <= V[g]);
else x = p;
}
x = Lpar[0][Lpar[0][x]];
}
ans -= Ldep[x];
x = Lpos[m];
p = Lpar[0][x];
if (Lmin[x] + d <= V[x] && -min_seg.query(1, 1, n, x + 1, m) + d <= V[x]);
else if (p && Lmin[p] + d <= V[p] && Lmin[x] + d <= V[p]) x = p;
else {
for (int i = 20; i--; ) {
int p = Lpar[i][x];
int g = Lpar[0][p];
if (!g) continue;
if (Lmin[g] + d <= V[g] && Lmin[p] + d <= V[g]);
else x = p;
}
x = Lpar[0][Lpar[0][x]];
}
ans += Ldep[x];
return ans;
}
} L, R;
void init(int N, vector<int> H) {
n = N;
L.init(H);
reverse(H.begin(), H.end());
R.init(H);
}
int max_towers(int L, int R, int D) {
++L;
++R;
int V = ::L.max_seg.query(1, 1, n, L, R);
int M = ::L.max_seg.find(1, 1, n, R, V - 1);
return ::L.query(M, R, D) + ::R.query(n + 1 - M, n + 1 - L, D) + (V - D >= -::L.min_seg.query(1, 1, n, L, M - 1) && V - D >= -::L.min_seg.query(1, 1, n, M + 1, R)) + 1;
}
