#include "towers.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
const int MAX=2e5+10;
const int inf=1e9;
struct segtree{
int mx[4*MAX],mn[4*MAX],pmx[4*MAX];
void build(int v,int tl,int tr,vector<int> &H){
if(tl==tr){
mx[v]=mn[v]=H[tl];
pmx[v]=tl;
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm,H);
build(2*v+1,tm+1,tr,H);
mx[v]=max(mx[2*v],mx[2*v+1]);
if(mx[2*v]>mx[2*v+1])pmx[v]=pmx[2*v];
else pmx[v]=pmx[2*v+1];
mn[v]=min(mn[2*v],mn[2*v+1]);
}
int getMn(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return inf;
if(l<=tl&&tr<=r)return mn[v];
int tm=(tl+tr)/2;
return min(getMn(2*v,tl,tm,l,r),getMn(2*v+1,tm+1,tr,l,r));
}
pii getMx(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return {-inf,-inf};
if(l<=tl&&tr<=r)return {mx[v],pmx[v]};
int tm=(tl+tr)/2;
return max(getMx(2*v,tl,tm,l,r),getMx(2*v+1,tm+1,tr,l,r));
}
}T;
int n,root;
vector<int> g[MAX];
int p[MAX];
int posMx=0;
bool sub;
vector<int> h;
int make_tree(int l,int r){
if(l>r)return -1;
auto [mx,pos]=T.getMx(1,0,n-1,l,r);
int pos1=make_tree(l,pos-1);
int pos2=make_tree(pos+1,r);
if(pos1!=-1){
g[pos].pb(pos1);
}
if(pos2!=-1)g[pos].pb(pos2);
return pos;
}
void init(int N, vector<int> H) {
sub=1;
int cnt=0;
for(int i=1;i<N-1;i++){
if(H[i]>H[i-1]&&H[i]>H[i+1]){
cnt++;
// cout<<H[i-1]<<" "<<H[i]<<" "<<H[i+1]<<"\n";
}
}
if(N>1){
cnt+=(H[1]<H[0]);
// cout<<(H[1]<H[0])<<"\n";
cnt+=(H[N-2]<H[N-1]);
// cout<<(H[N-2]<H[N-1])<<"\n";
}
// cout<<cnt<<"\n";
if(cnt!=1)sub=0;
for(int i=0;i<N;i++){
if(H[i]>H[posMx])posMx=i;
}
h=H;
T.build(1,0,N-1,H);
n=N;
root=make_tree(0,n-1);
p[0]=g[0].empty();
for(int i=1;i<N;i++)p[i]=p[i-1]+(g[i].empty());
}
int get(int l,int r,int d,int g){
if(l>r)return 0;
int ans=0;
if(T.getMn(1,0,n-1,l,r)<=g){
ans=1;
}
auto [mx,pos]=T.getMx(1,0,n-1,l,r);
ans=max(ans,get(l,pos-1,d,mx-d)+get(pos+1,r,d,mx-d));
return ans;
}
int get1(int l,int r){
if(l==r)return 1;
int ans=p[r]-(l>0?p[l-1]:0);
if(sz(g[l])==1&&g[l][0]<l)ans++;
if(sz(g[r])==1&&g[r][0]>r)ans++;
return ans;
}
int max_towers(int L, int R, int D) {
if(sub){
if(L<posMx&&posMx<R){
if(h[posMx]-D>=max(h[L],h[R]))return 2;
return 1;
}
else return 1;
}
if(D==1){
return get1(L,R);
}
return get(L,R,D,inf);
}
