#include "towers.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
vector<ll>v;
ll n;
const ll maxi = 5e5;
ll a[maxi];
ll st[4*maxi];
ll getmax(ll l, ll r, ll v, ll ql, ll qr)
{
if (l>qr or r<ql)
return INT_MIN;
if (l>=ql and r<=qr)
return st[v];
ll mid = (l+r)/2;
return max(getmax(l, mid, 2*v, ql, qr), getmax(mid+1, r, 2*v+1, ql, qr));
}
void update(ll l, ll r, ll v, ll ind, ll val)
{
if (ind<l or ind>r)
return;
if (l==r)
{
st[v] = val;
return;
}
ll mid = (l+r)/2;
update(l, mid, 2*v, ind, val);
update(mid+1, r, 2*v+1, ind, val);
st[v] = max(st[2*v], st[2*v+1]);
}
void init(int N, std::vector<int> H)
{
for (auto i:H) v.push_back(i);
n = N;
}
int max_towers(int L, int R, int D)
{
vector<ll>vs;
vs.push_back(0);
for (int i=L ; i<=R ; i++) vs.push_back(v[i]);
v = vs;
ll n = v.size()-1;
for (int i=1 ; i<=n ;i++)
update(1, n, 1, i, v[i]);
vector<ll>rg(n+1), lf(n+1);
for (int i=1 ; i<=n ; i++)
{
ll l = i+1, r = n;
ll best = -1;
while (l<=r)
{
ll mid = (l+r)/2;
ll val = getmax(1, n, 1, i, mid);
if (val>=v[i]+D)
{
best = mid;
r = mid-1;
}
else
l = mid+1;
}
rg[i] = best;
}
for (int i=1 ; i<=n ; i++)
{
ll l = 1, r = i-1;
ll best = -1;
while (l<=r)
{
ll mid = (l+r)/2;
ll val = getmax(1, n, 1, mid, i);
if (val>=v[i]+D)
{
best = mid;
l = mid+1;
}
else
r = mid-1;
}
lf[i] = best;
}
vector<ll>dp(n+1, 1), sv(n+1, 0);
ll res = 0;
for (int i=n ; i>=1 ;i--)
{
if (rg[i]!=-1) dp[i] = sv[rg[i]]+1;
if (lf[i]!=-1) sv[lf[i]] = max(sv[lf[i]], dp[i]);
if (i!=n) sv[i] = max(sv[i], sv[i+1]);
// cout<<dp[i]<<" ";
res = max(res, dp[i]);
}
return res;
}
