#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int DECALAGE=(1<<17);
int pb,avant,apres,rep;
vector<int> h;
vector<pair<int,int>> altitudes;
int arbremax[DECALAGE*2];
set<int> pris;
set<int>::iterator it;
int maxi(int deb,int fin){
if (deb==fin){
return arbremax[deb];
}
if (deb%2==1){
return max(arbremax[deb],maxi(deb+1,fin));
}
if (fin%2==0){
return max(arbremax[fin],maxi(deb,fin-1));
}
return maxi(deb/2,fin/2);
}
void init(int N,vector<int> H) {
h=H;
}
int max_towers(int L, int R, int D) {
for (int i=L;i<=R;i++){
altitudes.push_back(make_pair(h[i],i));
arbremax[i+DECALAGE]=h[i];
}
for (int i=DECALAGE-1;i>=0;i--){
arbremax[i]=max(arbremax[i*2],arbremax[i*2+1]);
}
sort(altitudes.begin(),altitudes.end());
for (int i=0;i<(int)altitudes.size();i++){
it=pris.lower_bound(altitudes[i].second);
pb=0;
if (it!=pris.end()){
apres=*(it);
if (maxi(altitudes[i].second+DECALAGE,apres+DECALAGE)-altitudes[i].first<D){
pb=1;
}
}
if (it!=pris.begin()){
it--;
avant=*(it);
if (maxi(avant+DECALAGE,altitudes[i].second+DECALAGE)-altitudes[i].first<D){
pb=1;
}
}
if (pb==0){
pris.insert(altitudes[i].second);
rep++;
}
}
return rep;
}
