#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int n;
vector<int> seg;
void init (int n_) {
n = n_;
seg.resize(n * 2 - 1);
build();
}
void build(int nd, int l, int r) {
seg[nd] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build(nd + 1, l, mid);
build(rs, mid + 1, r);
}
void build() {
build(0, 0, n - 1);
}
void upd (int nd, int l, int r, int p, int v) {
if (l == r) {
seg[nd] = v;
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p, v);
} else {
upd(rs, mid + 1, r, p, v);
}
seg[nd] = max(seg[nd + 1], seg[rs]);
}
void upd(int p, int v) {
upd(0, 0, n - 1, p, v);
}
int qry (int nd, int l, int r, int s, int e) {
if (l >= s && r <= e) return seg[nd];
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
return qry(nd + 1, l, mid, s, e);
} else {
if (mid < s) {
return qry(rs, mid + 1, r, s, e);
} else {
return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
}
}
}
int qry(int s, int e) {
return qry(0, 0, n - 1, s, e);
}
};
vector<int> a;
vector<int> b;
SegTree not_matched;
SegTree not_complete;
void init(int N, std::vector<int> H) {
a = b = H;
sort(b.begin(), b.end());
not_matched.init(N);
not_complete.init(N);
}
int get_ind(int value) {
return upper_bound(b.begin(), b.end(), value) - b.begin() - 1;
}
int get_ind2(int value) {
return lower_bound(b.begin(), b.end(), value) - b.begin();
}
int max_towers(int L, int R, int D) {
not_complete.build();
not_matched.build();
for (int i = L; i <= R; ++i) {
int match = get_ind(a[i] - D);
if (match >= 0) {
assert(match < (int) a.size());
int best = not_matched.qry(0, match);
not_complete.upd(get_ind(a[i]), best);
}
int complete = get_ind2(a[i] + D);
int best = 0;
if (complete < (int) a.size()) {
best = not_complete.qry(complete, (int) a.size() - 1);
}
not_matched.upd(get_ind(a[i]), best + 1);
}
return not_matched.seg[0];
}
