Why Did the Cow Cross the Road II.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

La gran carretera a través de la graja del Granjero Juan tiene N pasos peatonales a lo largo de ella, convenientemente numerados 1...N (1 \leq N \leq 100,000). Para permitir que las vacas crucen esos pasos, GJ instala señales eléctricas de cruce, las cuales se prenden con un icono de una vaca verde cuando es tiempo que las vacas crucen, y rojo en otro caso. Desafortunadamente, una gran tormenta eléctrica ha dañado algunas de sus señales. Dada una lista de señales dañadas, por favor calcule el número mínimo de señales que GJ necesita reparar para que hayan algún bloque contiguo de al menos K señales funcionando.

Entrada

La primera línea de la entrada contiene N, K, y B (1 \leq B, K \leq N). Las siguientes B líneas describen los números de identificación de una señal dañada.

Salida

Por favor calcule el número mínimo de señales que deben ser reparadas para que una un bloque contiguo de K señales funcionado en alguna parte de la carretera.

Ejemplo de Entrada

10 6 5
2
10
1
5
9

Ejemplo de Salida

1

Comments

There are no comments at the moment.