#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N, H[MAXN+10];
struct SEG
{
int tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]=H[tl];
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
int query(int node, int tl, int tr, int l, int r)
{
if(r<tl || tr<l) return 0;
if(l<=tl && tr<=r) return tree[node];
int mid=tl+tr>>1;
return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
}seg;
void init(int _N, vector<int> _H)
{
N=_N;
for(int i=1; i<=N; i++) H[i]=_H[i-1];
seg.init(1, 1, N);
}
int max_towers(int L, int R, int D)
{
L++; R++;
vector<pii> V;
vector<int> V2;
for(int i=L; i<=R; i++) V.push_back({H[i], i});
sort(V.begin(), V.end());
set<int> S;
for(auto it : V)
{
auto pt=S.lower_bound(it.second);
bool flag=true;
if(pt!=S.end())
{
int l=it.second, r=*pt;
if(seg.query(1, 1, N, l, r)-D<it.first) flag=false;
}
if(pt!=S.begin())
{
int l=*prev(pt), r=it.second;
if(seg.query(1, 1, N, l, r)-D<it.first) flag=false;
}
if(flag) S.insert(it.second), V2.push_back(it.second);
}
return S.size();
}
