#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int>A;
int n;
struct node {
int tree[4*MAXN];
void build(int node, int s, int e){
tree[node]=0;
if(s!=e){
int m=(s+e)/2;
build(node<<1,s,m);
build(node<<1|1,m+1,e);
}
}
void update(int node, int s, int e, int x, int nval){
if(s==e){
tree[node]=nval;
return;
}
int m=(s+e)/2;
if(x<=m)update(node<<1,s,m,x,nval);
else update(node<<1|1,m+1,e,x,nval);
tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
int query(int node, int s, int e, int x, int y){
if(s==x&&e==y)return tree[node];
int m=(s+e)/2;
if(y<=m)return query(node<<1,s,m,x,y);
else if(x>m)return query(node<<1|1,m+1,e,x,y);
else return max(query(node<<1,s,m,x,m),query(node<<1|1,m+1,e,m+1,y));
}
int walk(int node, int s, int e, int tar){
if(s==e)return s;
int m=(s+e)/2;
if(tree[node<<1|1]>=tar)return walk(node<<1|1,m+1,e,tar);
else return walk(node<<1,s,m,tar);
}
}seg,sa;
int ls[MAXN];
void init(int N, std::vector<int> H) {
n=N;
A=H;
}
typedef pair<int,int>pi;
int max_towers(int L, int R, int D) {
sa.build(1,0,n);
seg.build(1,0,n);
int dp[n+5];memset(dp,0,sizeof dp);
for(int i=0;i<n;i++)dp[i]=1;
int ans=1;
priority_queue<pi,vector<pi>,greater<pi>>pq;
for(int i=L;i<=R;i++){
int lf=sa.walk(1,0,n,A[i]+D);
if(L<=lf-1){
int mx=seg.query(1,0,n,L,lf-1);
dp[i]=max(dp[i],mx+1);
ans=max(ans,dp[i]);
}
while(pq.size() && pq.top().first <= A[i]-D){
pi cur=pq.top();pq.pop();
//cerr<<cur.second<<" "<<dp[cur.second]<<"\n";
seg.update(1,0,n,cur.second,dp[cur.second]);
}
sa.update(1,0,n,i,A[i]);
pq.push({A[i],i});
}
return ans;
}
