/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は山岳地帯のハイキングコースを歩く計画を立てています。
このコースは N 個の地点が一直線に並んでおり、地点 i（1 \leq i \leq N）の標高は H_i です。高橋君は地点 1 から出発し、地点 1, 2, \ldots, N の順に進んで地点 N まで歩きます。
高橋君は高所恐怖症であり、地点 i から地点 i+1 への移動（1 \leq i \leq N-1）において、標高が K 以上下がる場合（すなわち H_i - H_{i+1} \geq K となる場合）に恐怖を感じます。それ以外の移動では恐怖を感じません。
コースの管理者は、高橋君が恐怖を感じずに歩けるよう、地点 2, 3, \ldots, N-1 の中から任意の個数（0 個でもよい）の地点を選び、それぞれの標高を好きな非負整数値に変更できます。地点ごとに異なる値に変更してもよく、変更後の値に上限はありません。ただし、地点 1 と地点 N の標高は変更できません。
高橋君が一度も恐怖を感じることなく地点 1 から地点 N まで歩けるようにするために、標高を変更する地点数の最小値を求めてください。ただし、どのように標高を変更しても恐怖を回避できない場合は -1 を出力してください。
注意: N \geq 3 であっても -1 になる場合があります。変更できない地点 1 と地点 N の標高差が大きすぎると、中間地点の標高をどのように変更しても恐怖を回避できません。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq H_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数である
入力
N K H_1 H_2 \ldots H_N
1 行目には、地点の数 N と恐怖を感じる基準となる標高の下降量 K が、スペース区切りで与えられる。2 行目には、各地点の標高 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
出力
高橋君が一度も恐怖を感じずに地点 1 から地点 N まで歩けるようにするために、標高を変更する地点数の最小値を 1 行で出力せよ。ただし、恐怖を回避することが不可能な場合は -1 を出力せよ。
入力例 1
5 3 10 8 4 5 3
出力例 1
1
入力例 2
3 5 20 0 5
出力例 2
-1
入力例 3
12 4 15 13 9 12 8 6 10 5 4 7 3 2
出力例 3
4
入力例 4
30 7 100 95 90 82 85 78 70 72 65 60 54 58 50 49 42 35 38 31 25 20 23 18 12 10 5 8 3 2 1 0
出力例 4
8
入力例 5
2 1 0 0
出力例 5
0
Score : 433 pts
Problem Statement
Takahashi is planning to walk a hiking course in a mountainous area.
This course consists of N points arranged in a straight line, and the elevation of point i (1 \leq i \leq N) is H_i. Takahashi starts at point 1 and walks to point N by proceeding through points 1, 2, \ldots, N in order.
Takahashi has a fear of heights, and when moving from point i to point i+1 (1 \leq i \leq N-1), he feels fear if the elevation decreases by K or more (that is, if H_i - H_{i+1} \geq K). He does not feel fear during any other movements.
The course manager can select any number (possibly 0) of points from points 2, 3, \ldots, N-1 and change each of their elevations to any non-negative integer value, so that Takahashi can walk without feeling fear. Different points may be changed to different values, and there is no upper limit on the changed values. However, the elevations of points 1 and N cannot be changed.
Find the minimum number of points whose elevations need to be changed so that Takahashi can walk from point 1 to point N without ever feeling fear. If it is impossible to avoid fear no matter how the elevations are changed, output -1.
Note: Even when N \geq 3, the answer may be -1. If the elevation difference between the unchangeable points 1 and N is too large, fear cannot be avoided no matter how the elevations of intermediate points are changed.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N K H_1 H_2 \ldots H_N
The first line contains the number of points N and the elevation descent threshold K that triggers fear, separated by a space. The second line contains the elevations of each point H_1, H_2, \ldots, H_N, separated by spaces.
Output
Print in one line the minimum number of points whose elevations need to be changed so that Takahashi can walk from point 1 to point N without ever feeling fear. If it is impossible to avoid fear, output -1.
Sample Input 1
5 3 10 8 4 5 3
Sample Output 1
1
Sample Input 2
3 5 20 0 5
Sample Output 2
-1
Sample Input 3
12 4 15 13 9 12 8 6 10 5 4 7 3 2
Sample Output 3
4
Sample Input 4
30 7 100 95 90 82 85 78 70 72 65 60 54 58 50 49 42 35 38 31 25 20 23 18 12 10 5 8 3 2 1 0
Sample Output 4
8
Sample Input 5
2 1 0 0
Sample Output 5
0