C - ハードル走

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500

問題文

N 個のハードルが数直線上に置かれている。i 番目のハードルの位置は x_i で、 x_i は正の整数かつ x_1 < x_2 < … < x_N を満たす。

あなたはハードル走の走者である。あなたは数直線上の原点から正の方向に一定の速度で走って進む。途中で走る向きを変えることはできない。あなたは任意の位置(整数座標でなくともよい)でジャンプすることができる。ジャンプすると、そこから L メートルの間空中を移動したのち着地する。しかしジャンプは体力を使うので、着地してから L メートルの間はジャンプできず、地上を走らなければならない。最初、あなたは地上にいる。

あなたはハードルに当たることなくすべてのハードルを飛び越えることができるか?

ただし、位置 x にあるハードルを飛び越えるとは、位置 x で空中にいることである。また、ジャンプする位置、着地する位置ではあなたは地上にいるものとする。つまり、ハードルのある位置でジャンプしたり、ハードルのある位置に着地することはできない。原点でジャンプすることはできる。

制約

  • 入力は全て整数である。
  • 1 ≦ N ≦ 10^5
  • 1 ≦ L ≦ 10^9
  • 1 ≦ x_1 < x_2 < … < x_N ≦ 10^9

部分点

400 点分のテストケースでは、以下のすべてが満たされる。

  • 1 ≦ N ≦ 2000
  • 1 ≦ L ≦ 2000
  • 1 ≦ x_1 < x_2 < … < x_N ≦ 2000

入力

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

N L
x_1
x_2
:
x_N

出力

ハードルに当たることなくすべてのハードルを飛び越えることができる場合は”YES”(ダブルクオーテーションは不要), そうでない場合は”NO”を出力せよ。


入力例 1

3 4
3
5
13

出力例 1

YES

図1: 入力例1での飛び方の例

図1の赤い線はハードルを、青い線はすべてのハードルを飛び越えるための進み方の一例を示している。 この進み方では、まず 0 ≦ x ≦ 1.2 では地上を走る。 次に、x = 1.2 でジャンプする。すると 1.2 < x < 5.2 では空中を進む。ジャンプの影響により、 5.2 ≦ x ≦ 9.2 では地上を走らなければならない。 その後 x = 11 でジャンプすると、すべてのハードルを飛び越えることができる。

このケースは部分点の制約を満たす。


入力例 2

5 3
1
2
5
7
9

出力例 2

NO

どのようにジャンプしても位置 x = 5 のハードルを飛び越えることはできない。

このケースは部分点の制約を満たす。


入力例 3

5 6
1
2
3
4
5

出力例 3

YES

たとえば原点でジャンプするとすべてのハードルを飛び越えることができる。

このケースは部分点の制約を満たす。


入力例 4

3 5
1
3
10

出力例 4

NO

原点から負の方向に移動することはできない。

このケースは部分点の制約を満たす。


入力例 5

4 4
2
3
9
15

出力例 5

NO

このケースは部分点の制約を満たす。


入力例 6

4 1
1
3
5
7

出力例 6

YES

このケースは部分点の制約を満たす。


入力例 7

4 6100991
199010
199110
6300101
9231211

出力例 7

NO