分数: 300 点
问题陈述
Snuke 买了一座长度的桥 L。 他决定用长度为蓝色的防水布覆盖这座桥 W 每个。
下面,桥上的位置由距桥左端的距离表示。 当放置防水布时,其左端位于 x (0 \leq x \leq L-W, x 是真实的),它涵盖了范围 [x, x+W]。 (请注意,两端都包含在内。)
他已经放置了 N 防水布。 的左端 i-th 防水布位于该位置 a_i.
至少还需要多少防水布才能完全覆盖桥梁? 在这里,对于任何实数,桥梁被完全覆盖 x 之间 0 和 L (含),有防水布覆盖该位置 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
输出
打印完全覆盖桥梁所需的最少防水布数量。
示例输入 1
2 10 3 3 5
示例输出 1
2
- 桥梁将被完全覆盖,例如放置两块防水布,使其左端位于以下位置 0 和 7.
示例输入 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