#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h;
int n;
void init(int N, vector<int> H) {
n = N;
h = H;
}
struct SegmentTree {
int n;
vector<int> f;
SegmentTree(int n) : n(n), f(4 * n) {}
void modify(int p, int l, int r, int x, int y) {
if (l == r - 1) {
f[p] = y;
} else {
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, y);
} else {
modify(2 * p + 1, m, r, x, y);
}
f[p] = max(f[2 * p], f[2 * p + 1]);
}
}
void modify(int x, int y) {
modify(1, 0, n, x, y);
}
int rangeMax(int p, int l, int r, int x, int y) {
if (r <= x || y <= l) return 0;
if (x <= l && r <= y) return f[p];
int m = (l + r) / 2;
return max(rangeMax(2 * p, l, m, x, y), rangeMax(2 * p + 1, m, r, x, y));
}
int rangeMax(int l, int r) {
return rangeMax(1, 0, n, l, r);
}
};
int max_towers(int l, int r, int D) {
deque<pair<int, int>> st;
vector<int> nxt(n, -1);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && h[st.front().second] <= h[i]) st.pop_front();
st.push_front({h[i], i});
auto p = lower_bound(st.begin(), st.end(), pair{h[i] + D, -1});
if (p != st.end()) {
nxt[i] = p->second;
}
}
st.clear();
vector<int> prev(n, -1);
for (int i = 0; i < n; i++) {
while (!st.empty() && h[st.front().second] <= h[i]) st.pop_front();
st.push_front({h[i], i});
auto p = lower_bound(st.begin(), st.end(), pair{h[i] + D, -1});
if (p != st.end()) {
prev[i] = p->second;
}
}
vector<vector<int>> events(n);
vector<int> dp(n);
for (int i = l; i <= r; i++) {
if (nxt[i] != -1) {
events[nxt[i]].push_back(i);
}
}
SegmentTree s(n);
for (int i = l; i <= r; i++) {
// dp[i] = 1;
// for (int j = l; j < i; j++) {
// if (nxt[j] != -1 && prev[i] != -1 && nxt[j] < i && prev[i] > j) {
// dp[i] = max(dp[i], dp[j] + 1);
// }
// }
dp[i] = s.rangeMax(l, prev[i]) + 1;
for (auto j : events[i]) {
s.modify(j, dp[j]);
}
}
return *max_element(dp.begin(), dp.end());
}
