#include "towers.h"
#include "bits/stdc++.h"
using namespace std;
struct SegTeRan {
vector<int> a;
int get(int l, int r, int i, int lq, int rq) {
if (r <= lq || rq <= l) return 0;
if (lq <= l && r <= rq) return a[i];
int m = (l + r)/2;
return max(get(l, m, 2*i + 1, lq, rq), get(m, r, 2*i + 2, lq, rq));
}
int set(int l, int r, int i, int k, int v) {
if (k < l || r <= k) return a[i];
if (l + 1 == r) return a[i] = v;
int m = (l + r)/2;
return a[i] = max(set(l, m, 2*i + 1, k, v), set(m, r, 2*i + 2, k, v));
}
};
struct SegTeMa{
vector<int> a;
int build(int l, int r, int i, vector<int>& in) {
if (l + 1 == r) return a[i] = in[l];
int m = (l + r)/2;
return a[i] = max(build(l, m, 2*i + 1, in), build(m, r, 2*i + 2, in));
}
int firLe(int l, int r, int i, int k, int hi) {
if (l > k) return -1;
if (a[i] < hi) return -1;
if (l + 1 == r) return l;
int m = (l + r)/2;
int reR = firLe(m, r, 2*i + 2, k, hi);
if (reR != -1) return reR;
return firLe(l, m, 2*i + 1, k, hi);
}
int firRi(int l, int r, int i, int k, int hi) {
if (r <= k) return -1;
if (a[i] < hi) return -1;
if (l + 1 == r) return l;
int m = (l + r)/2;
int reR = firRi(l, m, 2*i + 1, k, hi);
if (reR != -1) return reR;
return firRi(m, r, 2*i + 2, k, hi);
}
};
vector<int> ch;
void init(int N, std::vector<int> H) {
SegTeMa maSe{vector<int>(4*N)};
SegTeRan raSe{vector<int>(4*N, 0)};
maSe.build(0, N, 0, H);
vector<int> o(N);
std::iota(o.begin(), o.end(),0);
std::sort(o.begin(), o.end(), [&](int l, int r){return H[l] < H[r];});
for (int i = 0; i < N; ++i) {
int l = 0, r = 1e9 + 1;
while (l + 1 < r) {
int m = l + (r - l)/2;
int leB = maSe.firLe(0, N, 0, o[i], H[o[i]] + m), reB = maSe.firRi(0, N, 0, o[i], H[o[i]] + m);
if (leB == -1) leB = 0;
if (reB == -1) reB = N;
if (raSe.get(0, N, 0, leB, reB) < m) l = m;
else r = m;
}
raSe.set(0, N, 0, o[i], l);
ch.push_back(l);
}
std::sort(ch.begin(), ch.end());
}
int max_towers(int L, int R, int D) {
return std::upper_bound(ch.rbegin(), ch.rend(),D, greater<>()) - ch.rbegin();
}
