/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は美術館の学芸員です。美術館には N 個の作品が展示候補としてあり、それぞれ 1 から N までの番号が付けられています。i 番目の作品の評価スコアは H_i です。
高橋君はこれらの作品の中から 1 個以上を選んで展示することにしました。同じ作品を複数回選ぶことはできません。選んだ作品は番号の小さい順に一列に並べて展示します（並び順を自由に変えることはできません）。
展示の統一感を保つために、並べた作品の列は以下の条件を満たす必要があります。
- 選んだ作品の個数を k（k \geq 1）とし、それらを番号の小さい方から順に a_1, a_2, \ldots, a_k（a_1 < a_2 < \cdots < a_k）とする。このとき、すべての 1 \leq j \leq k-1 について、|H_{a_j} - H_{a_{j+1}}| \leq D が成り立つ。
すなわち、番号順に並べた展示作品の列において、隣り合う 2 つの作品の評価スコアの差の絶対値がすべて D 以下でなければなりません。作品を 1 つだけ選ぶ場合、隣り合う組が存在しないため、この条件は自動的に満たされます。
高橋君は、できるだけ多くの作品を展示したいと考えています。上記の条件を満たしながら選べる作品の個数の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^9
- 1 \leq H_i \leq 10^9
- 入力はすべて整数である。
入力
N D H_1 H_2 \ldots H_N
- 1 行目には、作品の個数を表す整数 N と、隣り合う作品間で許容される評価スコアの差の絶対値の上限（以下）を表す整数 D が、スペース区切りで与えられる。
- 2 行目には、各作品の評価スコアを表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
出力
条件を満たしながら選べる作品の個数の最大値を 1 行で出力せよ。
入力例 1
5 3 4 1 5 8 3
出力例 1
3
入力例 2
5 0 3 1 3 3 2
出力例 2
3
入力例 3
10 5 10 3 8 12 7 15 9 6 11 2
出力例 3
7
入力例 4
20 10 50 45 55 40 35 30 25 20 28 33 38 43 48 53 58 63 68 60 55 50
出力例 4
19
入力例 5
1 0 1000000000
出力例 5
1
Score : 433 pts
Problem Statement
Takahashi is a curator at an art museum. The museum has N works as exhibition candidates, numbered from 1 to N. The evaluation score of the i-th work is H_i.
Takahashi has decided to select 1 or more works from these to exhibit. The same work cannot be selected more than once. The selected works are displayed in a row in ascending order of their numbers (the arrangement order cannot be freely changed).
To maintain a sense of unity in the exhibition, the sequence of arranged works must satisfy the following condition:
- Let k (k \geq 1) be the number of selected works, and let them be a_1, a_2, \ldots, a_k (a_1 < a_2 < \cdots < a_k) in ascending order of their numbers. Then, for all 1 \leq j \leq k-1, |H_{a_j} - H_{a_{j+1}}| \leq D must hold.
In other words, in the sequence of exhibited works arranged in order of their numbers, the absolute difference of evaluation scores between every two adjacent works must be at most D. When selecting only one work, there are no adjacent pairs, so this condition is automatically satisfied.
Takahashi wants to exhibit as many works as possible. Find the maximum number of works that can be selected while satisfying the above condition.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^9
- 1 \leq H_i \leq 10^9
- All input values are integers.
Input
N D H_1 H_2 \ldots H_N
- The first line contains an integer N representing the number of works and an integer D representing the upper limit (inclusive) of the absolute difference of evaluation scores allowed between adjacent works, separated by a space.
- The second line contains integers H_1, H_2, \ldots, H_N representing the evaluation scores of each work, separated by spaces.
Output
Output the maximum number of works that can be selected while satisfying the condition, in a single line.
Sample Input 1
5 3 4 1 5 8 3
Sample Output 1
3
Sample Input 2
5 0 3 1 3 3 2
Sample Output 2
3
Sample Input 3
10 5 10 3 8 12 7 15 9 6 11 2
Sample Output 3
7
Sample Input 4
20 10 50 45 55 40 35 30 25 20 28 33 38 43 48 53 58 63 68 60 55 50
Sample Output 4
19
Sample Input 5
1 0 1000000000
Sample Output 5
1