#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define bit(x, i) ((x >> i) & 1)
template<typename T>
using vec = vector<T>;
vec<int> h_;
int n_;
int peak;
void init(int N, std::vector<int> H) {
h_ = H;
n_ = N;
peak = max_element(h_.begin(), h_.end()) - h_.begin();
}
template<typename it>
struct SparseTable {
using T = typename remove_reference<decltype(*declval<it>())>::type;
vector<vector<T>> t;
function<T(T, T)> f;
vector<int> log;
SparseTable() = default;
SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
int n = distance(first, last);
t.assign(32 - __builtin_clz(n), vector<T>(n));
t[0].assign(first, last);
log.resize(n + 1);
for (int i = 2; i <= n; i++)
log[i] = log[i / 2] + 1;
for (int i = 1; i < t.size(); i++)
for (int j = 0; j < n - (1 << i) + 1; j++)
t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
}
T get(int l, int r) {
int h = log[r - l + 1];
return f(t[h][l], t[h][r - (1 << h) + 1]);
}
};
const int maxN = 1e5 + 10;
int stree[4 * maxN];
void init() {
memset(stree, -1e9, sizeof stree);
}
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
stree[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) update(2 * v, tl, tm, pos, val);
else update(2 * v + 1, tm + 1, tr, pos, val);
stree[v] = max(stree[2 * v], stree[2 * v + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
if (l > r) return -1e9;
if (tl == l && tr == r) return stree[v];
int tm = (tl + tr) / 2;
return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
int cnt = 0;
int max_towers1(int L, int R, int D) {
if (L < peak and R > peak) {
if (h_[peak] >= max(h_[L], h_[R]) + D) {
return 2;
}
return 1;
}
return 1;
}
int max_towers2(int L, int R, int D) {
vec<int> h;
for (int i = L; i <= R; i++) h.push_back(h_[i]);
int n = h.size();
init();
SparseTable stmax(h.begin(), h.end(), [](int a, int b) { return max(a, b); });
vec<int> dp(n, 0);
multiset<pair<int, int>> ms;
for (int i = n - 1; i >= 0; i--) {
dp[i] = 1;
if (i == n - 1) {
ms.insert({h[i], i});
continue;
}
int tl = i + 1;
int tr = n - 1;
if (stmax.get(tl, tr) < h[i] + D) {
while (!ms.empty()) {
auto [val, idx] = *ms.begin();
if (h[i] < val + D) break;
ms.erase(ms.begin());
update(1, 0, n - 1, idx, dp[idx]);
}
ms.insert({h[i], i});
}
while (tl != tr) {
int tm = (tl + tr) / 2;
if (stmax.get(i + 1, tm) >= h[i] + D) tr = tm;
else tl = tm + 1;
}
dp[i] = max(dp[i], get(1, 0, n - 1, tl + 1, n - 1) + 1);
while (!ms.empty()) {
auto [val, idx] = *ms.begin();
if (h[i] < val + D) break;
ms.erase(ms.begin());
update(1, 0, n - 1, idx, dp[idx]);
}
ms.insert({h[i], i});
// int cur_max = h[i + 1];
// for (int j = i + 2; j < n; j++) {
// if (cur_max >= max(h[i], h[j]) + D) {
// dp[i] = max(dp[i], dp[j] + 1);
// }
// cur_max = max(cur_max, h[j]);
// }
}
return *max_element(dp.begin(), dp.end());
}
int max_towers(int L, int R, int D) {
if (cnt > 1) {
return max_towers1(L, R, D);
} else {
cnt++;
return max_towers2(L, R, D);
}
}
