#include "towers.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
using namespace std;
struct SegTree{
int N;
vector<int>tree;
int merge(int a,int b){
return max(a,b);
}
void build(int n){
N=1;
while(N<n) N<<=1;
tree.assign(2*N,0);
}
void update(int v,int l,int r,int id,int x){
if(r-l==1){
tree[v]=x;
return;
}
int mid=(l+r)/2;
if(id<mid) update(v<<1,l,mid,id,x);
else update(v<<1|1,mid,r,id,x);
tree[v]=merge(tree[v<<1],tree[v<<1|1]);
}
void update(int id,int x){
return update(1,0,N,id,x);
}
int get(int v,int l,int r,int ql,int qr){
if(ql>=r || l>=qr) return 0;
if(l>=ql && qr>=r) return tree[v];
int mid=(l+r)/2;
return merge(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid,r,ql,qr));
}
int get(int l,int r){
return get(1,0,N,l,r);
}
};
int n,k;
vector<int>h;
bool su1=true;
void init(int N, std::vector<int> H) {
n=N;
h=H;
k=0;
bool ok=true;
for(int i=1;i<n;i++){
if(h[i]>h[i-1] && ok) k=i;
else{
if(h[i]>h[i-1]) su1=false;
ok=false;
}
}
}
int max_towers(int L, int R, int D) {
if(su1){
if(L<k && R>k && h[k]-D>=h[L] && h[k]-D>=h[R]) return 2;
return 1;
}
vector<int>a,dp(R-L+1);
dp[0]=1;
for(int i=L;i<=R;i++){
a.push_back(h[i]);
}
// map<int,int>mp;
// vector<int>b=a;
// sort(b.begin(),b.end());
// int c=0;
// for(int x:b) m[x]=c++;
// SegTree S;
// S.build(c);
int ans=1,mx=0;
set<pair<int,int>>s={{a[0],0}};
for(int i=1;i<a.size();i++){
dp[i]=mx;
dp[i]++;
ans=max(ans,dp[i]);
s.insert({a[i],i});
while(a[i]-D>=(*s.begin()).first){
auto x=*s.begin();
mx=max(mx,dp[x.second]);
s.erase(s.begin());
}
}
return ans;
}
