#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 69;
int a[maxn];
int n;
map <int, int> mp, inv;
vector <int> b;
int dp[maxn][2];
int seg[4 * maxn][2];
void upd(int l, int r, int pos, int qp, int v, int i){
if (l == r){
seg[pos][i] = v;
return;
}
int mid = (l + r)/2;
if (qp <= mid) upd(l, mid, pos*2, qp, v, i);
else upd(mid + 1, r, pos*2 + 1, qp, v, i);
seg[pos][i] = max(seg[pos * 2][i], seg[pos * 2 + 1][i]);
}
int query(int l, int r, int pos, int ql, int qr, int i){
if (l >= ql && r <= qr) return seg[pos][i];
else if (l > qr || r < ql) return 0;
int mid = (l + r)/2;
return max(query(l, mid, pos*2, ql, qr, i), query(mid + 1, r, pos*2 + 1, ql, qr, i));
}
void init(int N, vector<int> H) {
n = N;
for (int i = 0; i < N; i++){
a[i + 1] = H[i];
}
set <int> st;
for (int i = 1; i <= n; i++) st.insert(a[i]);
int ptr = -1;
st.insert(-1e9);
st.insert(2e9 + 1);
for (auto x : st){
mp[x] = ++ptr;
inv[ptr] = x;
b.push_back(x);
}
for (int i = 1; i <= n; i++) {
a[i] = mp[a[i]];
}
}
int max_towers(int l, int r, int d) {
l++;
r++;
int ans = 0;
for (int i = l; i <= r; i++){
int x = inv[a[i]];
int pos = upper_bound(b.begin(), b.end(), x - d) - b.begin() - 1;
dp[i][0] = query(1, n, 1, 1, pos, 0);
upd(1, n, 1, a[i], dp[i][0], 1);
pos = lower_bound(b.begin(), b.end(), x + d) - b.begin();
dp[i][1] = 1 + query(1, n, 1, pos, n, 1);
upd(1, n, 1, a[i], dp[i][1], 0);
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
