#include "towers.h"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
constexpr ll inf = 1e18;
template<class M>
class SegmentTree {
using T = typename M::T;
int n;
vector<T> dat;
public:
SegmentTree(int n_, T x) {
n = 1;
while (n < n_) n *= 2;
dat.assign(2 * n, x);
}
void set(int k, T x) {
k += n;
dat[k] = x;
while (k > 1) {
k /= 2;
dat[k] = M::op(dat[2 * k], dat[2 * k + 1]);
}
}
void apply(int k, T x) { set(k, M::op(dat[k + n], x)); }
T prod(int l, int r) const {
l += n; r += n;
T lsm = M::id(), rsm = M::id();
while (l < r) {
if (l & 1) lsm = M::op(lsm, dat[l++]);
if (r & 1) rsm = M::op(dat[--r], rsm);
l >>= 1; r >>= 1;
}
return M::op(lsm, rsm);
}
T all_prod() const { return dat[1]; }
};
struct Max {
using T = ll;
static T op(T a, T b) { return max(a, b); }
static T id() { return -inf; }
};
int N;
vector<int> H, Hs;
void init(int N_, std::vector<int> H_) {
N = N_; H = H_;
Hs = H;
sort(all(Hs));
Hs.erase(unique(all(Hs)), Hs.end());
rep (i, N) H[i] = lower_bound(all(Hs), H[i]) - Hs.begin();
}
int max_towers(int L, int R, int D) {
++R;
SegmentTree<Max> seg1(N + 1, -inf), seg2(N + 1, -inf);
seg2.set(N, 0);
rep2 (i, L, R) {
ll t = seg2.prod(lower_bound(all(Hs), Hs[H[i]] + D) - Hs.begin(), N + 1) + 1;
seg1.set(H[i], t);
t = seg1.prod(0, upper_bound(all(Hs), Hs[H[i]] - D) - Hs.begin());
seg2.set(H[i], t);
}
return seg1.all_prod();
}
