#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue
template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;
#include "towers.h"
struct ST {
int N;
vi tr, tr2;
ST() {}
ST(vi &A) {
int n = A.size();
for (N=1; N<n; N*=2);
tr.resize(2*N);
f0r(i, n) tr[N+i] = A[i];
tr2 = tr;
for (int i = N-1; i >= 0; --i) {
tr[i] = max(tr[2*i], tr[2*i+1]);
tr2[i] = min(tr2[2*i], tr2[2*i+1]);
}
}
#define m (l+r)/2
int queryL(int x, int ql, int qr, int v, int l, int r) {
if (tr[v] < x || qr < l || r < ql) return -1;
if (l == r) return l;
int re = queryL(x, ql, qr, 2*v, l, m);
return re != -1 ? re : queryL(x, ql, qr, 2*v+1, m+1, r);
}
int queryR(int x, int ql, int qr, int v, int l, int r) {
if (tr[v] < x || qr < l || r < ql) return -1;
if (l == r) return l;
int re = queryR(x, ql, qr, 2*v+1, m+1, r);
return re != -1 ? re : queryR(x, ql, qr, 2*v, l, m);
}
int query(int ql, int qr, int v, int l, int r) {
if (qr < l || r < ql) return 1e9;
if (ql <= l && r <= qr) return tr2[v];
return min(query(ql, qr, 2*v, l, m), query(ql, qr, 2*v+1, m+1, r));
}
#undef m
int queryL(int x, int ql, int qr) {
return queryL(x, ql, qr, 1, 0, N-1);
}
int queryR(int x, int ql, int qr) {
return queryR(x, ql, qr, 1, 0, N-1);
}
int query(int ql, int qr) {
return query(ql, qr, 1, 0, N-1);
}
};
V<pi> srt;
ST st;
int n;
int ss;
vi A;
vi pf;
void init(int N, std::vector<int> H) {
pf = vi(N+1);
f0r(i, N) pf[i+1] = pf[i] + ( (!i || H[i] < H[i-1]) && (i == N-1 || H[i] < H[i+1]));
A = H;
ss = max_element(all(H)) - begin(H);
n = N;
st = ST(H);
srt.clear();
f0r(i, N) srt.pb({H[i], i});
sort(all(srt));
}
int max_towers(int L, int R, int D) {
if (D == 1) return pf[R+1] - pf[L];
//return (L <= ss && ss <= R && A[L] + D <= A[ss] && A[R] + D <= A[ss]) ? 2 : 1;
int cnt = 0;
for (auto &[x, i]: srt) if (L <= i && i <= R) {
int l = st.queryR(x+D, L, i-1), r = st.queryL(x+D, i+1, R);
if (l == -1) l = L;
if (r == -1) r = R;
if (st.query(l, r) >= x) {
++cnt;
}
}
return cnt;
}
