#include "towers.h"
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
const int N = 1e5 + 2;
int d , n;
vector<int> h;
bool fr;
int sp[N][19] , lg[N] , spr[N][19];
vector<int> gg;
pair<int , int> p[N];
int get(int l , int r){
if(r < l) return -1;
int b = lg[r - l + 1];
return max(sp[l][b] , sp[r - (1 << b) + 1][b]);
}
int getr(int l , int r){
if(r < l) return 1e9;
int b = lg[r - l + 1];
return min(spr[l][b] , spr[r - (1 << b) + 1][b]);
}
void init(int N, std::vector<int> H) {
for(auto to : H) h.push_back(to);
n = N;
fr = false;
lg[0] = -1;
for(int i = 1;i <= n; ++ i){
lg[i] = lg[i / 2] + 1;
sp[i - 1][0] = h[i - 1];
}
for(int i = 1;i <= 18; ++ i){
int b = (1 << (i - 1));
for(int j = 0;j < n; ++ j){
if(j + b * 2 > n) break;
sp[j][i] = max(sp[j][i - 1] , sp[j + b][i - 1]);
}
}
}
int max_towers(int L, int R, int D) {
d = D;
vector<pair<pair<int , int> , int>> v;
set<pair<int , int>> st;
for(int i = L;i <= R; ++ i){
bool ok = true;
int l = L - 1;
int r = i;
while(l + 1 < r){
int mid = (l + r) / 2;
if(get(mid , i) >= h[i] + d) l = mid;
else r = mid;
}
p[i].fi = l;
l = i;
r = R + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(get(i , mid) >= h[i] + d) r = mid;
else l = mid;
}
p[i].se = r;
}
for(int i = L;i <= R; ++ i){
bool ok = true;
for(int j = L;j <= R; ++ j){
if((p[i].fi <= p[j].fi and p[i].se >= p[j].se) and (p[i].fi != p[j].fi or p[i].se != p[j].se)) ok = false;
}
if(ok){
st.insert({p[i].fi , p[i].se});
}
}
fr = true;
return st.size();
}
