#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<int> R, L;
int idx;
int N;
void init(int _N, std::vector<int> _H) {
N = _N;
a = _H;
// cerr << "H = ";
// for (auto& u : a) {
// cerr << u << " ";
// }
// cerr << "\n";
}
int max_towers(int l, int r, int D) {
int res = 1;
vector<pair<int, int>> tw;
vector<int> idx;
idx.push_back(l - 1);
for (int i = l + 1; i < r; ++i) {
if (a[i - 1] < a[i] && a[i] > a[i + 1]) {
tw.push_back({a[i], tw.size()});
idx.push_back(i);
}
}
idx.push_back(r + 1);
sort(rbegin(tw), rend(tw));
vector<int> mn((int)tw.size() + 1, 1e9 + 1);
int ptr = 0;
for (int i = 1; i < (int)idx.size(); ++i) {
int st = idx[i - 1] + 1;
int en = idx[i] - 1;
// cerr << "[" << st << " , " << en << "]: ";
for (int j = st; j <= en; ++j) {
// cerr << j << " = " << a[j] << " , ";
mn[ptr] = min(mn[ptr], a[j]);
}
// cerr << "\n";
ptr += 1;
}
// cerr << "mn = ";
// for (auto& u : mn) {
// cerr << u << " ";
// }
// cerr << "\n";
// cerr << "tw =\n";
// for (auto& [u, i] : tw) {
// cerr << u << " " << i << "\n";
// }
// cerr << "\n";
priority_queue<pair<int, int>> pq;
vector<bool> active(tw.size() + 1);
int now = 0;
for (auto& [u, i] : tw) {
while (pq.size() && pq.top().first + D > u) {
int j = pq.top().second;
if (active[j]) {
active[j] = false;
now -= 1;
}
pq.pop();
}
if (mn[i] + D <= u) {
if (!active[i]) {
active[i] = true;
now += 1;
pq.push({mn[i], i});
}
}
if (mn[i + 1] + D <= u) {
if (!active[i + 1]) {
active[i + 1] = true;
now += 1;
pq.push({mn[i + 1], i + 1});
}
}
res = max(res, now);
}
return res;
}
