2825 - 信号塔

题目描述

在一条直线上有 N 个信号塔,编号为 1 \sim N,按照编号从小到大的顺序,均匀分布在该直线上。

由于遇到了极寒天气,有 X 个不同的信号塔出现了故障。

电信公司将紧急维修任务下发到了当地的维修队,要求维修队在最短的时间内维修其中的部分信号塔。维修任务要求在维修后,必须存在连续的 L 个信号塔是可以正常工作的。

时间紧,任务重,人手有限,维修队长找到了维修队中唯一会编程的你,请你编程计算一下,最少要维修多少个信号塔,才能满足维修任务的要求?

输入

1 行读入 3 个整数,NLX,含义如题所述。

接下来 X 行,每行有一个整数,代表了出现故障的信号塔的编号。

输出

输出一个整数,代表为了达到维修任务的要求,最少要维修的信号塔的数量。

样例

输入

10 5 6
2
10
8
6
7
4

输出

2
说明

【样例解释】

维修 1 号到 5 号信号塔中的 2 号、4 号两个信号塔,可以使得 1 号到 5 号,这 5 个连续的信号塔都能正常工作。

【数据范围】

对于 30\% 的数据 1 \le N \le 3000

对于 100\% 的数据,1 \le N \le 10^51 \le X,L \le N

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 508
通过人数 224
金币数量 2 枚
难度 基础


上一题 下一题