#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
int N;
vector<int> H;
void init(int N_, vector<int> H_)
{
N = N_;
H = H_;
}
int max_towers(int L, int R, int D)
{
// You should always lease the smallest tower
// No two adjacent towers can be leased
int res = 0;
vector<int> leased(N);
vector<int> taken(N);
while (true)
{
int mn = INF;
int mn_index = -1;
for (int i = L; i <= R; i++)
{
if (!leased[i] && !taken[i] && H[i] < mn)
{
mn = H[i];
mn_index = i;
}
}
if (mn == INF) break;
bool ok = true;
int mx = mn;
for (int i = mn_index + 1; i <= R; i++)
{
if (leased[i])
{
if (mx - mn < D)
{
taken[mn_index] = 1;
ok = false;
}
break;
}
else
{
mx = max(mx, H[i]);
}
}
if (!ok)
continue;
mx = mn;
for (int i = mn_index - 1; i >= L; i--)
{
if (leased[i])
{
if (mx - mn < D)
{
taken[mn_index] = 1;
ok = false;
}
break;
}
else
{
mx = max(mx, H[i]);
}
}
if (!ok) continue;
res++;
leased[mn_index] = 1;
if (mn_index > L) taken[mn_index-1] = 1;
if (mn_index < R) taken[mn_index+1] = 1;
}
return res;
}
