Colorado の Farmer Ron は牛のスキー場を作りますが、予算でリフトは一つだけです。モノレールで始点のコンクリート支柱から中間支柱を経て終点へつなぎ、各支柱は地面から高さ0です。隣接支柱を直線の鋼材でつなぎ、当然全点が地面より上です。

倹約家 FR は支柱を最小化したいです。通る等大の $N$ 区画 $(2 \le N \le 5,000)$ を調査し、整数高さ $H$ $(0 \le H \le 1,000,000,000)$ を記録しました。安全規則で隣接距離は $K$ 単位以下 $(1 \le K \le N - 1)$。鋼材は剛体で直線です。

鋼材が全区画より上か接し、隣接水平距離が $K$ 以下、最初と最後の区画に支柱がある最小支柱数を求めてください。

入力

• $1$ 行目：空白区切り2整数 $N$、$K$。
• $2..N+1$ 行目：$i+1$ 行目は区画 $i$ の高さの整数一つ。

出力

• $1$ 行目：上の条件で最小の支柱数。

入出力例

入力 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

出力 1

5

注記

1、5、7、9、13に5本建て、鋼材は1–5、5–7、7–9、12–13の4か所で地面に接します。

1、5、9、13の4本だと5–9で地下です。1、7、13では鋼材は上ですが7と13の水平距離が4超です。隣接距離4以下で5本未満の解はありません。

原題出典：https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

問題作成者：Adam Rosenfield, 2004