問題文

アスラットは一次元上の位置 \(0\) にいて、位置 \(G\) まで行きたいです。アスラットは \(1\) 秒間に \(1\) だけ進むことができます。

一次元上には \(N\) 個のハードルがあり、 \(i\) 番目のハードルは位置 \(x_i\) にあります。

アスラットは足を怪我している状態で、今のままではハードルのある位置を通過することは出来ません。

アスラットの守護神であるフラッカーは任意のタイミングで治療能力を使うことができますが、それは一時的なもので一定時間後にその効き目は切れてしまいます。

具体的には、治療能力を使うと治療能力を使ったタイミングから \(K\) 秒間は左足が使えるようになり、ハードルを壊して突き進むことができるようになりますが、 \(K\) 秒経った後は元通り左足が使えなくなってハードルのある位置を通過することができなくなってしまいます。

(治療能力を使ったタイミングから丁度 \(K\) 秒後には、ハードルのある位置を通過することはできません)

フラッカーは治療能力を使う回数を出来るだけ少なくしたいです。

フラッカー(とアスラット)のために治療能力を使う回数の最小値を求めるプログラムを作ってあげましょう。

入力

\(N\) \(G\) \(K\)

\(x_1\) \(x_2\) \(...\) \(x_N\)

出力

治療能力を使う回数の最小値を1行に出力しなさい。

制約

• \(1≦N≦10^5\)


• \(1≦G≦10^9\)


• \(1≦x_1< x_2< ... < x_N< G\)


• \(1≦K≦10^9\)

小課題

小課題 Small

• \(1≦G≦16\)

小課題 Large

• \(1≦G≦10^5\)

小課題 Hard Hurdle

• \(G=N+1\)

小課題 Short Duration

• \(K=1\)

小課題 Euglena

• 追加の制約はない。