#include "towers.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;
constexpr int maxn = 1e5 + 5;
int n;
int h[maxn], ledge[maxn] = { 0 }, redge[maxn] = { 0 }, owner[maxn] = { 0 };
bool removed[maxn] = { 0 };
int out = 0;
void uni(int a, int b)
{
assert(a != b);
out--;
h[a] = min(h[a], h[b]);
ledge[a] = min(ledge[a], ledge[b]);
redge[a] = max(redge[a], redge[b]);
owner[ledge[a] + 1] = owner[redge[a] - 1] = a;
removed[b] = true;
}
vector <arr> output; // {d val, output}
void init(int N, std::vector<int> H) {
n = N;
for (int i = 0; i < n; i++) h[i + 1] = H[i];
h[0] = h[n + 1] = 2e9;
vector <arrr> edges; // {height diff, from, to}
edges.reserve(n - 1);
vector <int> minima;
for (int i = 1; i <= n; i++) {
if (h[i - 1] > h[i] && h[i] < h[i + 1]) {
minima.emplace_back(i);
}
}
priority_queue <arr, vector<arr>, greater<arr>> pq;
for (int i : minima)
{
ledge[i] = i - 1, redge[i] = i + 1;
owner[i] = i;
if (i != 1) pq.push(arr{h[ledge[i]] - h[i], i});
if (i != n) pq.push(arr{h[redge[i]] - h[i], i});
}
out = minima.size();
int d = 1;
arr a;
while (!pq.empty())
{
a = pq.top();
pq.pop();
if (removed[a[1]]) continue;
if (a[0] >= d) { // Might not get last
output.emplace_back(arr{d, out});
d = a[0] + 1;
}
// Left side
if (h[ledge[a[1]]] - h[a[1]] == a[0])
{
int i = ledge[a[1]] - 1;
while (i > 0 && owner[i] == 0 && h[i] <= h[ledge[a[1]]]) i--;
if (owner[i] != 0) {
uni(owner[i], a[1]);
if (ledge[owner[i]] != 0) pq.emplace(arr{h[ledge[owner[i]]] - h[owner[i]], owner[i]});
if (redge[owner[i]] != n + 1) pq.emplace(arr{h[redge[owner[i]]] - h[owner[i]], owner[i]});
} else if (h[i] > h[ledge[a[1]]])
{
ledge[a[1]] = i;
owner[i + 1] = a[1];
if (i != 0) pq.emplace(arr{h[i] - h[a[1]], a[1]});
}
}
// Right side
if (h[redge[a[1]]] - h[a[1]] == a[0])
{
int i = redge[a[1]] + 1;
while (i <= n && owner[i] == 0 && h[i] <= h[redge[a[1]]]) i++;
if (owner[i] != 0)
{
uni(a[1], owner[i]);
if (redge[a[1]] != n + 1) pq.emplace(arr{h[redge[a[1]]] - h[a[1]], a[1]});
if (ledge[a[1]] != 0) pq.emplace(arr{h[ledge[a[1]]] - h[a[1]], a[1]});
} else if (h[i] > h[redge[a[1]]])
{
redge[a[1]] = i;
owner[i - 1] = a[1];
if (i != n + 1) pq.emplace(arr{h[i] - h[a[1]], a[1]});
}
}
// cout << "a: " << a[0] << " " << a[1] << " " << ledge[a[1]] << " " << redge[a[1]] << "\n";
}
if (d != output.back()[0])
{
output.emplace_back(arr{d, out});
}
// for (auto &i : output) {
// cout << i[0] << " " << i[1] <<"\n";
// }
}
int max_towers(int l, int r, int d) {
if (r - l < 2) return 1;
auto it = lower_bound(output.begin(), output.end(), arr{d, (int)2e9}) - 1;
return (*it)[1];
}
