#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct Seg {
int siz = 1;
vector<int> sums;
void init(int n){
while(siz < n)siz*=2;
sums.assign(siz * 2, 0LL);
}
void build(vector<int>& arr , int x , int lx , int rx){
if(rx-lx==1){
if(lx < (int)arr.size()){
sums[x] = arr[lx];
}
return;
}
int m = (lx + rx) / 2;
build(arr , 2 * x + 1 , lx , m);
build(arr, 2 * x + 2 , m , rx);
sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
}
void build(vector<int>& arr){
build(arr , 0 , 0 , siz);
}
void set(int i , int v , int x , int lx , int rx){
if(rx - lx ==1){
sums[x] = v;
return;
}
int m = (lx + rx) / 2;
if(i < m){
set(i , v , 2 * x + 1 , lx , m);
}
else {
set(i , v , 2 * x + 2 , m , rx);
}
sums[x]=sums[2 * x + 1] + sums[2 * x + 2];
}
void set(int x , int y){
set(x ,y , 0 , 0 , siz);
}
int sum(int l , int r , int x , int lx , int rx){
if(lx >= l && rx <= r){
return sums[x];
}
if(lx >= r || rx <= l)return 0;
int m = (lx + rx) / 2;
return sum(l , r , 2 * x + 1 , lx , m) + sum(l , r , 2 * x + 2 , m , rx);
}
int sum(int l , int r){
return sum(l , r , 0 , 0 , siz);
}
};
vector<int> arr;
Seg st;
void init(int n, std::vector<int> h) {
arr = h;
st.init(n+1);
vector<int> a(n,0);
for(int i = 0; i < n; i++){
int cnt = 0;
if(i - 1 < 0 || arr[i] > arr[i-1])cnt++;
if(i + 1 == n || arr[i + 1] < arr[i])cnt++;
if(cnt == 2)a[i] = 1;
}
st.build(a);
}
int max_towers(int l , int r , int d) {
return min(r - l + 1 , 1 + st.sum(l , r+1));
}
