// komak!
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn5 = 1e5 + 10;
int mxid, h[maxn5];
int n, dp[maxn5], dp2[maxn5];
pair <int, int> per[maxn5];
void solve(int l, int r, int d){
if(r <= l)
return;
int mid = l;
for(int i = l + 1; i < r; i++)
if(h[i] > h[mid])
mid = i;
solve(l, mid, d);
solve(mid + 1, r, d);
for(int i = l; i < r; i++)
per[i] = {h[i], i};
sort(per + l, per + r);
int mx1 = 0, mx2 = 0;
for(int i = l; i < r; i++){
if(per[i].se < mid)
mx1 = max(mx1, dp[per[i].se]);
if(per[i].se > mid)
mx2 = max(mx2, dp[per[i].se]);
dp2[i] = max(mx1, mx2);
if(per[i].fi + d <= per[r - 1].fi)
dp2[i] = mx1 + mx2;
}
dp2[r - 1] = max(dp2[r - 1], 1);
for(int i = l; i < r; i++){
h[i] = per[i].fi;
dp[i] = dp2[i];
}
}
void init(int N, std::vector<int> H) {
mxid = 0;
n = N;
for(int i = 0; i < n; i++){
h[i] = H[i];
if(h[i] > h[mxid])
mxid = i;
}
}
int max_towers(int l, int r, int d) {
solve(l, r + 1, d);
return (*max_element(dp, dp + n));
}
