配点 : $300$ 点

問題文

すぬけ君は長さ $L$ の橋を買いました。 すぬけ君は、この橋を長さ $W$ のシートで覆うことにしました。

すぬけ君がシートを橋の左端から実数 $x(0 \leq x \leq L-W)$ のところから設置すると、橋の左端から $x$ 以上 $x+W$ 以下の部分が覆われます(境界を含むことに注意してください)。

すぬけ君はすでに $N$ 枚のシートを設置しています。 $i$ 番目のシートは橋の左端から $a_i$ のところから設置されています。

この橋全体を覆うには少なくとも何枚のシートが追加で必要でしょうか？ 橋全体が覆われているとは、$0$ 以上 $L$ 以下の任意の実数 $x$ について、橋の左端から $x$ の部分を覆うようなシートが存在していることをいいます。

制約

• 与えられる入力は全て整数
• $1 \leq N \leq 10^{5}$
• $1 \leq W \leq L \leq 10^{18}$
• $0 \leq a_1 < a_2 < \cdots < a_N \leq L-W$

入力

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

$N$ $L$ $W$

$a_1$ $\cdots$ $a_N$

出力

橋全体を覆うのに追加で必要なシートの枚数の最小値を出力せよ。

2 10 3
3 5

2

• 例えば、左端から $0$、$7$ のところにシートを $1$ 枚ずつ設置すると橋全体を覆うことができます。

5 10 3
0 1 4 6 7

0

12 1000000000 5
18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402

199999992