#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using vi = vector<int>;
using vvi = vector<vi>;
struct SegTree {
int N, neutral;
vi st, arr;
function<int(int, int)> combine;
SegTree(int _N, vi _arr, function<int(int, int)> _combine, int _neutral) {
N = _N; arr = _arr; combine = _combine, neutral = _neutral;
st.assign(4 * N, 0);
build(0, 0, N);
}
SegTree() : N(0), neutral(0) {};
int build(int i, int l, int r) {
if (l + 1 == r) return st[i] = arr[l];
int m = l + (r - l) / 2;
return st[i] = combine(build(2 * i + 1, l, m), build(2 * i + 2, m, r));
}
int query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return neutral;
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return combine(query(2 * i + 1, l, m, ql, qr), query(2 * i + 2, m, r, ql, qr));
}
int update(int i, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return st[i];
if (l + 1 == r) return st[i] = arr[k] = v;
int m = l + (r - l) / 2;
return st[i] = combine(update(2 * i + 1, l, m, k, v), update(2 * i + 2, m, r, k, v));
}
int query(int l, int r) {
return query(0, 0, N, l, r);
}
void update(int k, int v) {
update(0, 0, N, k, v);
}
};
struct DSU {
int N;
vi par, siz, mv;
set<int> components;
DSU(int _N, vi _mv) {
N = _N;
par.resize(N); iota(par.begin(), par.end(), 0);
siz.assign(N, 1);
mv = _mv;
components = set<int>(all(par));
}
DSU() : N(0) {};
int find_set(int v) {
if (v == par[v]) return v;
return par[v] = find_set(par[v]);
}
void union_set(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] > siz[b]) {
siz[a] += siz[b];
par[b] = a;
mv[a] = min(mv[b], mv[a]);
components.erase(b);
} else {
siz[b] += siz[a];
par[a] = b;
mv[b] = min(mv[b], mv[a]);
components.erase(a);
}
}
}
};
int n;
vi h, cmp;
SegTree maxST;
function<int(int, int)> mx = [](int a, int b) {return max(a, b);};
int gidx(int v) {
auto it = lower_bound(all(cmp), v);
if (it == cmp.end()) return -1;
else return (int) (it - cmp.begin());
}
/*
If tower i is connected to tower j, and tower j is connected to tower k (i < m1 < j < m2 < k)
- tower i and k are connected through either m1 or m2
dp[i][peak] = largest value of dp[j][!peak] for j > i and h[j] <= h[i] - D
dp[i][!peak] = 1 + largest value of dp[j][peak] for j > i and h[j] >= h[i] + D
*/
void init(int N, vi H) {
n = N; h = H;
maxST = SegTree(n, h, mx, INT_MIN);
cmp = h;
sort(all(cmp));
for (int i = 0; i < n; i++) {
h[i] = lower_bound(all(cmp), h[i]) - cmp.begin();
}
}
int max_towers(int L, int R, int D) {
auto dsu = DSU(n, h);
vvi DP(2, vi(n, 0));
auto stPeak = SegTree(n, DP[0], mx, INT_MIN);
auto stTrough = SegTree(n, DP[1], mx, INT_MIN);
for (int i = R; i >= L; i--) {
int height = cmp[h[i]];
int low = gidx(height - D), high = gidx(height + D);
bool lowFine = low != -1 && cmp[low] <= height - D, highFine = high != -1 && cmp[high] >= height + D;
int vP = highFine ? stPeak.query(high, n) : -1;
int vT = lowFine ? stTrough.query(0, low+1) : -1;
if (lowFine) {
stPeak.update(h[i], vT);
}
if (highFine) {
stTrough.update(h[i], vP);
}
}
return max({1, stPeak.query(0, n), stTrough.query(0, n)});
}
