#include "towers.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, inf = 2e9,LIM = 2010;
int sel = 0;
vi edges[LIM];
int dp[LIM][LIM];
int n;
vi h;
vi vals;
void init(int N, std::vector<int> H) {
n = N;
h = H;
for (auto it : h) vals.push_back(it);
sort(all(vals));
}
int idx(int x) {
return upper_bound(all(vals),x)-vals.begin();
}
int cartesian(int L,int R) {
int mx = -1,pick = -1;
for (int i=L;i<=R;i++) {
if (h[i] > mx) {
pick = i;
mx = h[i];
}
}
if (L < pick) edges[pick].push_back(cartesian(L,pick-1));
if (pick < R) edges[pick].push_back(cartesian(pick+1,R));
return pick;
}
void dfs(int node,int p,int D) {
for (int i=1;i<=n;i++) dp[node][i] = 0;
vi opt1(n+1,0),opt2(n+1,0);
for (auto it : edges[node]) {
if (it == p) continue;
dfs(it,node,D);
for (int j = 1;j<=n;j++) {
if (h[node] >= vals[j-1]+D) {
opt1[j] += dp[it][j];
}
}
}
dp[node][idx(h[node])] = 1;
for (int i=2;i<=n;i++) dp[node][i]=max(dp[node][i],max(opt1[i],dp[node][i-1]));
}
int dnq(int L,int R,int D) {
for (int i=0;i<=n;i++) edges[i].clear();
int root = cartesian(L,R);
dfs(root,root,D);
return dp[root][n];
}
int max_towers(int L, int R, int D) {
return dnq(L,R,D);
}
