B58 - Jumping Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点: 1000

問題文

N 個の足場が横一列に並んでおり、左から順に 1 から N までの番号が付けられています。足場 1 がスタート地点、足場 N がゴール地点であり、足場 i はスタート地点から X_i メートルの位置にあります。

あなたは 1 回で L メートル以上 R メートル以下の距離を右方向にのみジャンプできるとき、スタートからゴールまで最小何回のジャンプで行けますか。ただし、与えられる入力において、スタートからゴールまで到達できることが保証されます。

制約

  • 入力はすべて整数である
  • 2 \leq N \leq 100000
  • 1 \leq L \leq R \leq 10^9
  • 0 = X_1 < X_2 < \cdots < X_N \leq 10^9
  • 与えられる入力において、スタートからゴールまで到達可能である

入力

入力は以下の形式で標準入力から与えられます。

N L R
X_1 X_2 \ldots X_N

出力

答えを出力してください。


入力例 1

5 20 40
0 20 30 60 70

出力例 1

2

まず 30 メートルの距離をジャンプして足場 3 に行き、次に 40 メートルの距離をジャンプして足場 5 に行くのが最適です。