#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
const int M = 1e5 + 1;
int n,fen[M],le[M],dp[M];
vector<int> a;
void modify(int p,int x)
{
while (p<=n)
fen[p]=max(fen[p],x),p+=p&-p;
}
int get(int p)
{
int ans=0;
while (p)
ans=max(ans,fen[p]),p^=p&-p;
return ans;
}
void init(int N, vector<int> A)
{
n=N,a=A;
}
int max_towers(int l, int r, int d)
{
set<pair<int,int>> se;
for (int i=r;i>=l;i--)
{
while (se.size() && se.begin()->first<=a[i]-d)
le[se.begin()->second]=i,se.erase(se.begin());
le[i]=-1,se.insert({a[i],i});
}
se.clear();
int ans=1;
for (int i=l;i<=r;i++)
{
dp[i]=get(le[i]+1)+1,ans=max(ans,dp[i]);
while (se.size() && se.begin()->first<=a[i]-d)
{
int i=se.begin()->second;se.erase(se.begin());
modify(i+1,dp[i]);
}
se.insert({a[i],i});
}
return ans;
}
