/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
1 から N までの番号がつけられた N 個の足場が一列に並んでいます。足場 i(1 \leq i \leq N) の高さは 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 に乗り、以下のように足場を移動することができます。
- 1 回目の移動: H_2 \leq H_1 -D かつ |2-1| \leq R であるため足場 2 に移動することができる。足場 1 から足場 2 に移動する。
- 2 回目の移動: H_3 \leq H_2 -D かつ |3-2| \leq R であるため足場 3 に移動することができる。足場 2 から足場 3 に移動する。
- 足場 3 の高さは 1 であるため、これ以上移動できない。
以上のように 2 回移動することができます。また、どのように移動する足場を選んでも 3 回以上移動することはできません。よって、2 を出力します。
入力例 2
13 3 2 13 7 10 1 9 5 4 11 12 2 8 6 3
出力例 2
3
Score : 500 points
Problem Statement
There are N scaffolds numbered from 1 to N arranged in a line. The height of scaffold i(1 \leq i \leq N) is H_i.
Takahashi decides to play a game of moving on the scaffolds. Initially, he freely chooses an integer i(1 \leq i \leq N) and gets on scaffold i.
When he is on scaffold i at some point, he can choose an integer j(1 \leq j \leq N) satisfying the following condition and move to scaffold j:
- H_j \leq H_i - D and 1 \leq |i-j| \leq R.
Find the maximum number of moves he can make when he repeats moving until he can no longer move.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq D,R \leq N
- H is a permutation of (1,2,\ldots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D R H_1 H_2 \ldots H_N
Output
Output the answer.
Sample Input 1
5 2 1 5 3 1 4 2
Sample Output 1
2
Takahashi initially gets on scaffold 1 and can move between the scaffolds as follows:
- First move: Since H_2 \leq H_1 -D and |2-1| \leq R, he can move to scaffold 2. Move from scaffold 1 to scaffold 2.
- Second move: Since H_3 \leq H_2 -D and |3-2| \leq R, he can move to scaffold 3. Move from scaffold 2 to scaffold 3.
- Since the height of scaffold 3 is 1, he can no longer move.
As shown above, he can move 2 times. Also, no matter how he chooses the scaffolds to move to, he cannot move 3 or more times. Therefore, output 2.
Sample Input 2
13 3 2 13 7 10 1 9 5 4 11 12 2 8 6 3
Sample Output 2
3