题目描述

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

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

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

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

输入格式

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

$N$ $L$ $W$ $a_1$ $\cdots$ $a_N$

输出格式

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

题目大意

有一块长度为 $L$ 的木板，还有 $n$ 块长度为 $W$ 的布。

现告诉你这 $n$ 块布的起始位置 $a_i$，表示其能覆盖 $[a_i,a_i + W]$ 这段区间。

求还需添加多少块长度为 $W$ 的布，才能将整块木板覆盖。

注意：这里的覆盖指的是将所有的线段覆盖，而不仅仅是点。

translate by WaterSun

2 10 3
3 5

2

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

提示

制約

• 与えられる入力は全て整数
• $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 $

Sample Explanation 1

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