Why Did the Cow Cross the Road II (Silver)#10536
A long road runs through Farmer John's farm and has crosswalks across it, conveniently numbered from to . To allow cows to cross safely at these crosswalks, FJ installs electric crossing signals that display a green cow icon when it is safe to cross and red otherwise.
Unfortunately, a severe electrical storm has damaged some of the signals. Given a list of the damaged signals, determine the minimum number of signals FJ must repair so that there is a contiguous block of at least working signals.
The first line contains three integers: , and b~(1 \le n \le 10^5, 1 \le b, k \le n). Each of the next lines contains the ID number of a damaged signal.
Print the minimum number of signals that must be repaired so that there is a contiguous block of at least working signals somewhere along the road.
Пример 1