#include<bits/stdc++.h>
using namespace std;
// Observation 1: For every 2 towers we pick (i, j) |i - j| > 1 -> this means they cannot be adjacent.
// Observation 2: Can(a, b) ^ Can(b, c) => Can(a, c) (so you only care if adjacent pairs can)
int subtask1 = 0;
int subtask2 = 0;
int n;
int point_k;
int h[1000000];
int que = 0;
void is1(int N, std::vector<int> H){
std::vector<int> isDec(N); // it should be decreasing to the right
// so it should be increasing if we look at it from right.
isDec[N - 1] = 1;
for(int i = N - 2;i >= 0;i--){
isDec[i] = (isDec[i + 1] & (H[i] > H[i + 1]));
}
int inc = 1;
point_k = 0;
for(int i = 0;i < N;i++){
if(H[i] == H[i - 1]) break;
if(i > 0) inc &= (H[i] > H[i - 1]);
if(isDec[i] && inc){
subtask1 = 1;
point_k = i;
}
}
}
int do1(int L, int R, int D){
if(!(L <= point_k && point_k <= R)) return 1;
if(L == point_k || R == point_k) return 1;
return (h[L] <= h[point_k] - D && h[R] <= h[point_k] - D) ? 2 : 1;
}
void is2(int N){
subtask2 |= (N <= 2000);
}
int do2(int L, int R, int D){
int ans = 1;
std::vector<int> dp(n);
dp[L] = 1;
for(int i = L + 1;i <= R;i++){
dp[i] = 1;
int mx = h[i - 1] - D;
for(int j = i - 2;j >= 0;i--){
if(h[i] <= mx && h[j] <= mx) dp[i] = max(dp[i], dp[j] + 1);
mx = max(mx, h[j] - D);
}
ans = max(ans, dp[i]);
}
return ans;
}
void init(int N, std::vector<int> H){
is1(N, H);
is2(N);
n = N;
for(int i = 0;i < n;i++){
h[i] = H[i];
}
}
int max_towers(int L, int R, int D){
if(subtask1){ // we have a mountain.
return do1(L, R, D);
}
que++;
if(que == 1 && subtask2){
return do2(L, R, D);
}
assert(false);
return 1;
}
