#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9
int n;
vector <int> a;
void init(int N, vector<int> H) {
n = N;
a.resize(n);
for (int i = 0; i < n; i++){
a[i] = H[i];
}
}
int max_towers(int l, int r, int d) {
int ans = 1;
int best = INF;
int mx = -INF;
for (int i = l; i <= r; i++){
if (max(a[i], best) + d <= mx){
ans++;
best = a[i];
mx = -INF;
} else {
if (a[i] < best){
best = a[i];
mx = -INF;
} else {
mx = max(mx, a[i]);
}
}
}
return ans;
}
// int brute(int l, int r, int d){
// vector <int> dp(n);
// int ans = 0;
// for (int i = l; i <= r; i++){
// dp[i] = 1;
// for (int j = l; j < i; j++){
// bool good = false;
// for (int k = j; k <= i; k++){
// good |= a[k] >= max(a[i], a[j]) + d;
// }
// if (good){
// dp[i] = max(dp[i], dp[j] + 1);
// }
// }
// ans = max(ans, dp[i]);
// }
// return ans;
// }
// mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
// void solve(){
// // int n; cin >> n;
// int n = 1 + RNG() % 3;
// vector <int> A(n);
// for (int i = 0; i < n; i++){
// // cin >> A[i];
// A[i] = 1 + RNG() % 20;
// }
// init(n, A);
// // int q; cin >> q;
// int q = 10;
// while (q--){
// // int l, r, d; cin >> l >> r >> d;
// int l = RNG() % n;
// int r = RNG() % n;
// if (l > r) swap(l, r);
// int d = 1 + RNG() % 10;
// if (max_towers(l, r, d) != brute(l, r, d)){
// cout << "WA\n";
// cout << n << "\n";
// for (int i = 0; i < n; i++){
// cout << A[i] << " \n"[i + 1 == n];
// }
// cout << l << " " << r << " " << d << "\n";
// cout << max_towers(l, r, d) << " " << brute(l, r, d) << "\n";
// exit(0);
// }
// }
// }
// int main(){
// int t; cin >> t;
// while (t--){
// solve();
// }
// return 0;
// }
