#include "towers.h"
#include <bits/stdc++.h>
#define pb push_back
#define left (h<<1),l ,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define s second
#define f first
using namespace std;
const int N = 100005;
int n,a[N],l,r,d,L[N],R[N],t[4*N];
bool b[N];
vector <pair<pair<int,int>,int> > val;
struct {
int maxr;
int maxl;
} T[4*N];
void upd(int h,int l,int r,int idx){
if (l == r){
T[h].maxl = l;
T[h].maxr = l;
return;
}
if (idx > (l+r)/2) upd(right,idx);
else upd(left,idx);
//maxl
if (b[T[h*2].maxl]) T[h].maxl = T[h*2].maxl;
else if (b[T[h*2 + 1].maxl]) T[h].maxl = T[h*2+1].maxl;
else T[h].maxl = 0;
//maxr
if (b[T[h*2+1].maxr]) T[h].maxr = T[h*2+1].maxr;
else if (b[T[h*2].maxr]) T[h].maxr = T[h*2].maxr;
else T[h].maxr = 0;
}
int getmaxl(int h,int l,int r,int L,int R){
if (r < L || R < l) return 0;
if (L <= l && r <= R) return T[h].maxl;
int x = getmaxl(left,L,R),y = getmaxl(right,L,R);
if (b[x]) return x;
if (b[y]) return y;
return 0;
}
int getmaxr(int h,int l,int r,int L,int R){
if (r < L || R < l) return 0;
if (L <= l && r <= R) return T[h].maxr;
int x = getmaxr(left,L,R),y = getmaxr(right,L,R);
if (b[y]) return y;
if (b[x]) return x;
return 0;
}
void find(){
for (int i =1;i<=n;i++)
b[i]=0;
for (int j = 0;j < val.size(); j++){
int tp = val[j].f.s,id = val[j].s;
if (tp == 2){
b[id] = 1;
upd(1,1,n,id);
}else{
L[id] = getmaxr(1,1,n,l,id - 1);
R[id] = getmaxl(1,1,n,id + 1,r);
if (!L[id]) L[id] = l;
if (!R[id]) R[id] = r;
}
}
}
void build(int h,int l,int r){
if (l== r){
t[h]=a[l];
return;
}
build(left),build(right);
t[h] = min(t[h*2],t[h*2+1]);
}
int getmin(int h,int l,int r,int L,int R){
if (r < L || R < l) return 1e9;
if (L <= l && r <= R) return t[h];
return min(getmin(left,L,R),getmin(right,L,R));
}
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; i++)
a[i] = H[i-1];
build(1,1,n);
}
int max_towers(int lf, int rg, int D) {
l=lf+1,r=rg+1,d=D;
vector <pair<int,int> > vec;
vec.clear(); val.clear();
for (int i = l; i <= r; i++){
val.pb({{a[i]-d,2},i});
val.pb({{a[i],1},i});
vec.pb({a[i],i});
}
using P = pair<pair<int,int>,int> ;
sort(val.begin(),val.end(), greater <P> ());
sort(vec.begin(),vec.end());
find();
int ans=0;
for (auto [x,id]: vec)
if (getmin(1,1,n, L[id], R[id]) >= x) ans++;
return ans;
}
