#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> pr, h;
const int K = 17;
vector<pair<int, int>> sp[K];
vector<int> spm[K];
inline int msb(int x){
return 31-__builtin_clz(x);
}
int que(int l, int r){
int d = msb(r-l+1);
return max(sp[d][l], sp[d][r-(1<<d)+1]).second;
}
int qum(int l, int r){
int d = msb(r-l+1);
return min(spm[d][l], spm[d][r-(1<<d)+1]);
}
bool sub1 = true;
int th;
void init(int N, std::vector<int> H) {
h = H;
pr.resize(N);
pr[0]=0;
auto mx = max_element(H.begin(), H.end());
if(is_sorted(H.begin(), mx) && is_sorted(mx, H.end(), greater<int>())) {
sub1=true;
th = mx-H.begin();
}
else sub1=false;
for(int i = 0;i < K;i++) {
sp[i].resize(N);
spm[i].resize(N);
}
for(int i = 0;i < N;i++){
sp[0][i] = {H[i], i};spm[0][i]=H[i];
}
for(int k = 1;k < K;k++){
for(int i = 0;i+(1<<k)<=N;i++){
sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<k-1)]);
spm[k][i] = min(spm[k-1][i], spm[k-1][i+(1<<k-1)]);
}
}
for(int i = 1;i < N-1;i++){
pr[i]=pr[i-1];
if(H[i] < H[i-1] && H[i] < H[i+1]) pr[i]++;
}
}
int de;
int ans(int l, int r, int atm){
if(l==r){
if(h[l]<=atm) return 1;
return 0;
}
int m = que(l, r);
if(l==m) return ans(l+1, r, atm);
if(m==r) return ans(l, r-1, atm);
return max(ans(l, m-1, h[m]-de)+ans(m+1, r, h[m]-de), (qum(l,r) <= atm ? 1 : 0));
}
int max_towers(int L, int R, int D) {
if(sub1){
if(L>th || R < th) return 1;
return max(1, int(lower_bound(h.begin()+L, h.begin()+th+1, h[th]-D+1)-h.begin()-L+ h.begin()+R+1-lower_bound(h.begin()+th, h.begin()+R+1, h[th]-D, greater<int>())));
}
de = D;
if(L+1>=R) return 1;
if(D==1) return pr[R-1]-pr[L]+(h[L] < h[L+1])+(h[R]<h[R-1]);
return ans(L, R, INT_MAX);
}
