3223. 超光速列车

单点时限: 2.0 sec

内存限制: 256 MB

从上海到慕尼黑的超光速列车,由于运营成本大,涉及多方利益,所以采取不定期运营的方式(运营的日期是不固定的),但是运营时刻表是固定的。具体来说,如果决定今天要运营,那么必有一班列车 9:00 从上海开往慕尼黑,此列车会在 15:00 返回上海;如果决定今天不运营,那么两班列车都不开。

约翰叔叔在慕尼黑担任高官,能决定列车运营的日期,所以他想要稍微地利用一下这点权力。在接下来的 $n$ 天里,约翰叔叔将会有一段连续的 $r$ 天假期。他有一个侄女,在上海读大学,他想在这 $r$ 天内乘超光速列车往返一趟上海。由于约翰叔叔还不知道假期会从哪一天开始,所以他要为每种可能的情况都做好准备。

已经决定要运营的日子有 $k$ 天。因为票已经公开出售了,所以约翰叔叔不能取消这 $k$ 天的列车。他只能通过增加列车来满足自己的需求。请问他最少要增加多少天的列车呢?

输入格式

第一行含有三个整数,$n, k, r$ $(2 \leq n \leq 10^5, 0 \leq k \leq n, 2 \leq r \leq n)$。

接下来 $k$ 行,每行一个整数 $a_i$ $(1 \leq a_i \leq n)$,表示第 $a_i$ 天已经开设了列车。输入保证 $a_i$ 各不相同。

输出格式

输出还需要增加列车的天数。

样例

Input
15 5 4
2
5
7
10
13
Output
3

提示

样例中可能的一种情况:增设第 3 天的列车、第 9 天的列车、第 14 天的列车,就可以做到在任意 4 天内都能往返。

49 人解决,59 人已尝试。

60 份提交通过,共有 286 份提交。

4.1 EMB 奖励。

创建: 7 年,5 月前.

修改: 7 年,1 月前.

最后提交: 10 月,1 周前.

来源: Pacific NW 2016

题目标签