题目描述

すぬけ君买了一座长度为 $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$ $a_2$ $\cdots$ $a_N$

输出格式

请输出为了覆盖整座桥还需要额外铺设的防护布的最小数量。

样例 1

输入

2 10 3
3 5

输出

2

样例 2

输入

5 10 3
0 1 4 6 7

输出

0

样例 3

输入

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$

样例说明 1

例如，可以在左端 $0$ 和 $7$ 的位置各铺设一块防护布，这样就能覆盖整座桥。

由 ChatGPT 4.1 翻译