#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>H,addto;
void init(int N, std::vector<int> H_) {
H=H_;
}
struct fenwickt{
int T[100100];
int qry(int n){
n++;
int ans=0;
while(n)
ans=max(ans,T[n]),n-=n&-n;
return ans;
}
void upd(int n,int p){
n++;
while(n<100100)
T[n]=max(T[n],p),n+=n&-n;
}
} ST;
vector<pair<int,int>>inser[100100];
int max_towers(int l, int r, int D) {
int n=H.size();
vector<int>stk;
stk.push_back(n);
H.push_back(2e9);
addto.resize(n);
for(int i=r;i>=l;i--){
while(H[stk.back()]<H[i])
stk.pop_back();
H[i]+=D;
addto[i]=*--upper_bound(stk.begin(),stk.end(),i,[](int a,int b){
return H[a]>H[b];
});
H[i]-=D;
stk.push_back(i);
}
int ans=0;
stk.clear();
for(int i=l;i<=r;i++){
for(auto[pos,v]:inser[i])
ST.upd(pos,v);
while(stk.size()&&H[stk.back()]<H[i])
stk.pop_back();
H[i]+=D;
auto it=upper_bound(stk.begin(),stk.end(),i,[](int a,int b){
return H[a]>H[b];
});
H[i]-=D;
int Pos=0;
if(it!=stk.begin())
Pos=*--it;
int dp=ST.qry(Pos-1)+1;
inser[addto[i]+1].push_back({i,dp});
ans=max(ans,dp);
stk.push_back(i);
}
return ans;
}
