分数: 500 点
问题陈述
有 N 脚手架编号为 1 to N 排成一排。脚手架高度 i(1 \leq i \leq N) is H_i.
高桥决定玩一个在脚手架上移动的游戏。 最初,他自由选择一个整数 i(1 \leq i \leq N) 并登上脚手架 i.
当他在脚手架上时 i 在某个时刻,他可以选择一个整数 j(1 \leq j \leq N) 满足以下条件并移至脚手架 j:
- H_j \leq H_i - D 和 1 \leq |i-j| \leq R.
求当他重复移动直到不能再移动时他可以移动的最大次数。
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq D,R \leq N
- H 是一个排列 (1,2,\ldots,N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N D R H_1 H_2 \ldots H_N
输出
输出答案。
示例输入 1
5 2 1 5 3 1 4 2
示例输出 1
2
高桥最初登上脚手架 1 并且可以在脚手架之间移动,如下所示:
- 第一步:自 H_2 \leq H_1 -D 和 |2-1| \leq R,他可以移动到脚手架 2。从脚手架上移出 1 到脚手架 2.
- 第二步:自 H_3 \leq H_2 -D 和 |3-2| \leq R,他可以移动到脚手架 3。从脚手架上移出 2 到脚手架 3.
- 自脚手架高度 3 is 1,他不能再动了。
如上图,他可以移动 2 次。而且,无论他如何选择要移动到的脚手架,他都无法移动 3 或多次。因此,输出 2.
示例输入 2
13 3 2 13 7 10 1 9 5 4 11 12 2 8 6 3
示例输出 2
3