Bajtazarは、大量の砂利を安く購入できる絶好の機会を得ました。彼はこれを使って庭の小道を平らにしようと考えています。この小道は $n$ 個の区画からなり、それぞれの初期の高さは $a_1, \dots, a_n$ です。砂利をトラック1台分追加するごとに、ある区画の高さを1だけ上げることができます。Bajtazarは、小道が急勾配にならないようにしたいと考えています。つまり、隣接する区画の高さの差は最大でも $k$ でなければなりません。目的を達成するために、Bajtazarが購入しなければならない砂利のトラック数は最小でいくつでしょうか。

入力

入力の1行目には、2つの整数 $n$ と $k$ ($1 \le n \le 1\,000$ かつ $0 \le k \le 1\,000\,000$) が与えられます。これらはそれぞれ小道の長さと、隣接する区画間で許容される最大の高さの差を表します。入力の2行目には、$n$ 個の整数 $a_i$ ($0 \le a_i \le 1\,000\,000$) が与えられます。これらは各区画の初期の高さです。

出力

小道を平らにするために必要な砂利のトラック数の最小値を、整数で1つ出力してください。

入出力例

入力 1

4 2
7 3 0 2

出力 1

5

注記

例の解説：2番目の区画の高さを2上げて5にし、3番目の区画の高さを3上げて3にすることができます。小道のどの区画の高さも下げることは許可されていないことに注意してください。