#include "towers.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
vector<int> h;
void init(int N, std::vector<int> H) {
int n = N;
H.insert(H.begin(), 1e9);
H.push_back(1e9);
h = H;
// p.resize(n+1);
// for (int i=2; i<=n-1; i++) {
// if (H[i] < min(H[i+1], H[i-1])) {
// p[i]++;
// }
// }
// partial_sum(p.begin(), p.end(), p.begin());
}
int max_towers(int L, int R, int D) {
L++, R++;
int d = D;
vector<int> a(h.begin() + L, h.begin() + R+1);
int n = a.size();
a.insert(a.begin(), 1e9);
a.push_back(1e9);
vector<int> o(n);
iota(o.begin(), o.end(), 1);
sort(o.begin(), o.end(), [&] (int i, int j) {return a[i] < a[j];});
vector<int> v(n+2);
int ans = 0;
for (int i: o) {
int l = i-1, r = i+1;
while (a[l] < a[i] + d) l--;
while (a[r] < a[i] + d) r++;
int sum = accumulate(v.begin() + l+1, v.begin() + r, 0ll);
if (sum) continue;
for (int j=l+1; j<r; j++) v[j] = 1;
ans++;
}
return ans;
}
