#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001;
#include "towers.h"
struct Sparsetable{
ll n;
vvi tablema,tablemi;
vi sz;
void init(vi v){
n=v.size();
tablema=vvi(18,vi(n));tablemi=vvi(18,vi(n));
tablema[0]=tablemi[0]=v;
rep(i,17)rep(j,n)if(j+(1<<(i+1))<=n){
tablema[i+1][j]=max(tablema[i][j],tablema[i][j+(1<<i)]);
tablemi[i+1][j]=min(tablemi[i][j],tablemi[i][j+(1<<i)]);
}
sz=vi(n+1);
rep(i,18)REP(j,1<<i,1<<(i+1))if(j<=n)sz[j]=i;
}
ll getma(ll l,ll r){
if(l>=r)return -inf;
ll res=-inf;
REP(i,l,r)chmax(res,tablema[0][i]);
return res;
///////////////////////////////////////////////////////////
ll s=sz[r-l];
return max(tablema[s][l],tablema[s][r-(1<<s)]);
}
ll getmi(ll l,ll r){
if(l>=r)return inf;
ll res=inf;
REP(i,l,r)chmin(res,tablemi[0][i]);
return res;
///////////////////////////////////////////////////////////
ll s=sz[r-l];
return min(tablemi[s][l],tablemi[s][r-(1<<s)]);
}
};
vi v,sp,dif;
vvi L,R;
ll n,m;
Sparsetable sps;
void init(int N,vector<int> H){
for(int x:H)v.pb(-x);
sps.init(v);
n=N;
rep(i,n)if((i==0||v[i-1]>v[i])&&(i==n-1||v[i+1]>v[i]))sp.pb(i);
m=sp.size();
L=vvi(18,vi(m,-1));R=vvi(18,vi(m,-1));
{
vi st;
for(int i=m-1;i>=0;i--){
while(st.size()&&v[sp[st.back()]]>v[sp[i]])st.pop_back();
if(st.size())R[0][i]=st.back();
st.pb(i);
}
}
{
vi st;
rep(i,m){
while(st.size()&&v[sp[st.back()]]>v[sp[i]])st.pop_back();
if(st.size())L[0][i]=st.back();
st.pb(i);
}
}
rep(i,17)rep(j,m)if(L[i][j]!=-1)L[i+1][j]=L[i][L[i][j]];
rep(i,17)rep(j,m)if(R[i][j]!=-1)R[i+1][j]=R[i][R[i][j]];
dif=vi(m);
rep(i,m){
P rng;
rng.fi=(L[0][i]==-1 ? 0 : sp[L[0][i]]+1);
rng.se=(R[0][i]==-1 ? n-1 : sp[R[0][i]]-1);
ll ma=min(sps.getma(rng.fi,sp[i]),sps.getma(sp[i]+1,rng.se+1));
dif[i]=ma-v[sp[i]];
}
}
int max_towers(int a, int b, int D){
ll l=lb(sp,a),r=lb(sp,b+1)-1;
if(l>r)return 1;
ll l_=l,r_=r;
{
int cur=l;
while(cur!=-1&&cur<=r){
if(sps.getma(a,sp[cur])>=v[sp[cur]]+D)break;
l_=cur+1;
cur=R[0][cur];
}
}
{
int cur=r;
while(cur!=-1&&cur>=l){
if(sps.getma(sp[cur]+1,b+1)>=v[sp[cur]]+D)break;
r_=cur-1;
cur=L[0][cur];
}
}
int ans=0;
REP(i,l_,r_+1)if(dif[i]>=D)ans++;
return ans+1;
}
