← 返回题目列表

AtCoder · arc134_a

A. 桥和床单

中文机器翻译题面 查看原题

分数: 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