//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include"towers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
void precalc(){
}
#define MULTITESTS false
void solve(){
}
vector<int>val,pos;
int n;
vector<int>arr;
void build(int v,int l,int r){
if(l==r){
val[v]=arr[l];
pos[v]=l;
return;
}
int m=(l+r)/2;
build(2*v,l,m);
build(2*v+1,m+1,r);
pos[v]=pos[2*v+1];
val[v]=max(val[2*v],val[2*v+1]);
if(val[2*v]>val[2*v+1])pos[v]=pos[2*v];
}
int get(int v,int l,int r,int l0,int r0){
if(l==l0&&r==r0){
return pos[v];
}
int m=(l+r)/2;
if(r0<=m)return get(2*v,l,m,l0,r0);
else if(l0>m)return get(2*v+1,m+1,r,l0,r0);
int A=get(2*v,l,m,l0,m);
int B=get(2*v+1,m+1,r,m+1,r0);
int a=arr[A];
int b=arr[B];
return (a>b)?A:B;
}
void init(int N, std::vector<int> H){
arr.swap(H);
val.resize(4*N+5);
pos.resize(4*N+5);
n=N;
build(1,0,n-1);
}
map<vector<int>,int>mp;
int solve(int L,int R,int D,int LIM=2e9+5){
if(R<L)return 0;
if(L==R){
if(arr[L]<=LIM)return 1;
return 0;
}
if(mp.count({L,R,D,LIM}))return mp[{L,R,D,LIM}];
int p=get(1,0,n-1,L,R);
int res=max({
solve(L,p-1,D,LIM),
solve(p+1,R,D,LIM),
solve(L,p-1,D,min(LIM,arr[p]-D))+solve(p+1,R,D,min(LIM,arr[p]-D))
});
mp[{L,R,D,LIM}]=res;
return res;
}
int max_towers(int L, int R, int D){
return solve(L,R,D);
}
