#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e3+10;
int n, hx[N], mx[N][N];
void init(int _n, vector<int> _h) {
n=_n;
for (int i=1; i<=n; ++i) hx[i]=_h[i-1];
for (int i=1; i<=n; ++i) {
mx[i][i]=hx[i];
for (int j=i+1; j<=n; ++j) mx[i][j]=max(mx[i][j-1], hx[j]);
}
}
vector<int> G[N];
bool vis[N];
int dfs(int v) {
vis[v]=true;
int res=1;
for (auto u : G[v]) {
if (vis[u]) continue;
res+=dfs(u);
} return res;
}
int max_towers(int l, int r, int d) {
for (int i=0; i<=n; ++i) G[i].clear();
++l, ++r;
vector<pii> v;
for (int i=l; i<=r; ++i) v.push_back({hx[i], i});
sort(v.begin(), v.end());
bool us[n+1]={};
for (int i=l; i<=r; ++i) us[i]=true;
while (!v.empty()) {
pii x=v.back(); v.pop_back();
bool ok=true;
for (int i=l; i<=r; ++i) {
if (!us[i]) continue;
if (i == x.second) continue;
int j=x.second;
if (abs(i-j) == 1) ok=false;
if (i < j) {
if (max(hx[i], hx[j]) > mx[i+1][j-1]-d) ok=false;
} else {
if (max(hx[i], hx[j]) > mx[j+1][i-1]-d) ok=false;
}
}
if (!ok) us[x.second]=false;
}
int cnt=0;
for (int i=l; i<=r; ++i) cnt+=us[i];
return cnt;
}
