#include "towers.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 3000 + 10 , inf = 1e9+ 10 , mod = 998244353;
int mn[maxn][maxn] , n ;
vector <int> h ;
void init(int N, std::vector<int> H) {
n = N ;
h.pb(0);
rep(i , 0 , n-1)h.pb(H[i]) ;
rep(l , 1 ,n){
mn[l][l] = h[l];
mn[l][l-1] = inf ;
rep(r , l+1 ,n){
mn[l][r] = min(mn[l][r-1] ,h[r]) ;
}
}
mn[n+1][n] = inf ;
}
int solve(int l , int r ,int d){
int mx = l ;
rep(i, l ,r){
if(h[mx] < h[i])mx = i ;
}
if(mn[l][mx-1] + d > h[mx] && mn[mx+1][r]+ d > h[mx])return 1 ;
int sm =0 ;
if(mn[l][mx-1] + d <= h[mx])sm += solve(l,mx-1,d);
if(mn[mx+1][r] + d <= h[mx])sm += solve(mx+1,r,d);
return sm ;
}
int max_towers(int L, int R, int D) {
L++;
R++;
return solve(L,R,D);
}
