Bridge and Sheets

时间限制：2s
空间限制：1024MB

题目描述

有一座长度为 $L$ 的桥，其位置用从左端起的距离表示。每块防护布的长度均为 $W$；若一块防护布的左端放在实数位置 $x$（$0\le x\le L-W$），它会覆盖闭区间 $[x,x+W]$。

现在已经铺好了 $N$ 块防护布，第 $i$ 块的左端位于 $a_i$。求至少还需要铺多少块防护布，才能覆盖桥上的每一个位置。

输入格式

第一行输入三个整数 $N,L,W$。

第二行输入 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出还需增加的防护布数量的最小值。

样例输入 1

2 10 3
3 5

样例输出 1

2

样例输入 2

5 10 3
0 1 4 6 7

样例输出 2

0

样例输入 3

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

样例输出 3

199999992

数据范围

• $1\le N\le 10^5$；
• $1\le W\le L\le 10^{18}$；
• $0\le a_1<a_2<\cdots<a_N\le L-W$；
• 输入中的所有数均为整数。