[USACO17FEB] Why Did the Cow Cross the Road II S

题目描述

The long road through Farmer John's farm has $N$ crosswalks across it, conveniently numbered $1 \ldots N$ ($1 \leq N \leq 100,000$). To allow cows to cross at these crosswalks, FJ installs electric crossing signals, which light up with a green cow icon when it is ok for the cow to cross, and red otherwise. Unfortunately, a large electrical storm has damaged some of his signals. Given a list of the damaged signals, please compute the minimum number of signals that FJ needs to repair in order for there to exist some contiguous block of at least $K$ working signals. 共有N个信号灯,编号为1~N,有B个信号灯损坏,给你它们的编号。 问,最少修好几个信号灯,可以有K个编号连续的信号灯。

输入输出格式

输入格式


The first line of input contains $N$, $K$, and $B$ ($1 \leq B, K \leq N$). The next $B$ lines each describe the ID number of a broken signal

输出格式


Please compute the minimum number of signals that need to be repaired in order for there to be a contiguous block of $K$ working signals somewhere along the road.

输入输出样例

输入样例 #1

10 6 5
2
10
1
5
9

输出样例 #1

1

说明

感谢@ jlyzxxm1 提供题意简述