#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;
for(int i = L;i <= R; ++ i){
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;
// cout << get(i , mid) << ' ';
if(get(i , mid) >= h[i] + d) r = mid;
else l = mid;
}
p[i].se = r;
l = p[i].fi , r = p[i].se;
//cout << l << ' ' << r << '\n';
spr[i][0] = r;
if(v.size() == 0 or i > v.back().fi.se){
v.push_back({{l , r} , i});
}
else{
if(v.back().fi.fi >= l and v.back().fi.se <= r){
continue ;
}
else{
v.pop_back();
v.push_back({{l , r} , i});
}
}
}
fr = true;
return v.size();
}
