#include "towers.h"
#include <bits/stdc++.h>
using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(), a.end()
#define mp std::make_pair
#define pb emplace_back
constexpr ll inf = (1<<30)+(1<<29)+(1<<28);
ll N;
vi H;
ll D;
vi right, left;
constexpr ll di = 20;
ll sz;
vii pr, mr, pl, ml;
vii sum;
void init(int n, std::vector<int> h) {
N = n;
H.resize(N);
right.resize(N);
left.resize(N);
rep(i,0,N) H[i] = h[i];
D = -1;
}
int max_towers(int L, int R, int d) {
if(D == -1){
D = d;
{
sz = N/di+10;
/*
sum.resize(sz, vi(sz));
pr.resize(N+2);
mr.resize(N+2);
pl.resize(N+2);
ml.resize(N+2);*/
std::deque<ll> ima, vma, imi, vmi;
ima.pb(-3);
vma.pb(-inf);
imi.pb(-2);
vmi.pb(inf);
rep(i,0,N){
ll large = lower_bound(all(vmi), H[i]+D)-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small >= large) left[i] = small+1;
else left[i] = -1;
while(true){
if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
else break;
}
vma.pb(H[i]);
ima.pb(i);
while(true){
if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
else break;
}
vmi.emplace_front(H[i]);
imi.emplace_front(i);
}
}
{
std::deque<ll> ima, vma, imi, vmi;
ima.pb(N+3);
vma.pb(-inf);
imi.pb(N+2);
vmi.pb(inf);
per(i,N-1,0){
ll large = lower_bound(all(vmi), H[i]+D)-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small <= large) right[i] = small-1;
else right[i] = N;
while(true){
if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
else break;
}
vma.pb(H[i]);
ima.pb(i);
while(true){
if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
else break;
}
vmi.emplace_front(H[i]);
imi.emplace_front(i);
}
}
/*
rep(i,0,N){
left[i]++;
right[i]++;
ll ld = (left[i]+di-1)/di;
ll rd = right[i]/di;
sum[ld][rd]++;
ll id = i/di;
sum[ld][id]--;
id = (i+di-1)/di;
sum[id][rd]--;
pr[right[i]].pb(left[i]);
pl[left[i]].pb(right[i]);
ml[i+1].pb(right[i]);
ml[left[i]].pb(i+1);
mr[i+1].pb(left[i]);
mr[right[i]].pb(i+1);
}
REP(l,1,sz){
rep(i,0,sz){
ll j = i+l;
if(j >= sz) break;
sum[i][j] = sum[i+1][j]+sum[i][j-1]-sum[i+1][j-1];
}
}*/
}
ll ans = 0;
ll ld = (L+di-1)/di;
ll rd = R/di;
//ans = psum[ld][rd]-msum[ld][rd];
ans = 0;
rep(i,0,N){
if(left[i] <= L && R <= right[i]) ans++;
if(i+1 <= L && R <= right[i]) ans--;
if(left[i] <= L && R <= i-1) ans--;
}
return ans;
}
