#include "towers.h"

#include <vector>
#include<bits/stdc++.h>

namespace Sol{

using namespace std;
using ll=long long;
using u64=unsigned long long;
//using lll=__int128_t;
using lf=long double;
using Pr=pair<int,int>;
#define F(i,l,r) for(ll i=l;i<=ll(r);++i)
#define G(i,r,l) for(ll i=r;i>=ll(l);--i)
#define ct const
#define il inline
#define pb push_back
#define fi first
#define se second
#define mkr make_pair
template<class T>
il void tomn(T&x,T ct&y){y<x?x=y,0:0;}
template<class T>
il void tomx(T&x,T ct&y){x<y?x=y,0:0;}
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define CUT dbg("===================\n")
ct lf EPS=1e-10L;
il int dcmp(lf x){return fabs(x)<=EPS?0:(x<0?-1:1);}
//ct ll INF=4e18L;
ct int INF=1.02e9;
//il void rd(int&x){scanf("%d",&x);}
//il void rd(ll&x){scanf("%lld",&x);}

ct ll P=1000000007;
void add2(ll&x,ll y){x+=y,x-=((-(x>=P))&P);}
void sub2(ll&x,ll y){x-=y,x+=((-(x<0))&P);}
ll add(ll x,ll y){return add2(x,y),x;}
ll sub(ll x,ll y){return sub2(x,y),x;}

ct int N=1.02e5;
int n,h[N],l[N],r[N];
struct D{int x,i;};
struct Seg{int l,r;};
int qry(int s,int t,int d){
	static D st[N];
	int top;
	top=0,st[++top]=D{INF,0};
	F(i,1,n){
		for(;st[top].x<h[i];--top);
		st[++top]=D{h[i],(int)i};
		l[i]=(lower_bound(st,st+top+1,h[i]+d,[&](D d,int x){
			return d.x>=x;
		})-1)->i;
	}
	top=0,st[++top]=D{INF,n+1};
	G(i,n,1){
		for(;st[top].x<h[i];--top);
		st[++top]=D{h[i],(int)i};
		r[i]=(lower_bound(st,st+top+1,h[i]+d,[&](D d,int x){
			return d.x>=x;
		})-1)->i;
	}
	vector<Seg>vec;
	F(i,s,t)vec.pb(Seg{l[i],r[i]});
	sort(vec.begin(),vec.end(),[&](Seg x,Seg y){
		return x.r<y.r;
	});
	int lst=-INF,ans=0;
	for(Seg x:vec)if(x.l>=lst)
		++ans,lst=x.r;
	return ans;
}

}

void init(int N, std::vector<int> H) {
	using namespace Sol;
	n=N;
	F(i,1,n)h[i]=H[i-1];
}

int max_towers(int L, int R, int D) {
	return Sol::qry(L+1,R+1,D);
}