Muestreo de velociraptores (2) P85939

Es bien sabido que los velociraptores son una amenaza real y por ello hemos trazado un gran plan desde la OIE. Se ha descubierto un lugar donde, curiosamente, duermen cada noche n velociraptores en fila india. Sin embargo, la última misión fue un completo fracaso y vamos a probar de nuevo, cambiando un poco el objetivo.

Existen k especies distintas de velociraptor, y queremos capturar al menos un ejemplar de m especies diferentes. Por miedo a despertarlos, un requisito esencial es que todos los velociraptores capturados duerman consecutivamente. ¿Podéis decir el menor número que habrá que capturar?

Entrada

La entrada contiene diversos casos. Cada caso empieza con n, k y m. Finalmente, viene la especie de cada uno de los n velociraptores, en orden. Suponed 1 ≤ m ≤ k ≤ n ≤ 10⁶, que las especies se numeran entre 0 y k − 1, y que entre los n velociraptores hay al menos m de diferentes especies.

Salida

Para cada caso, escribid el menor número de velociraptores consecutivos que es necesario capturar.

Puntuación

• Test1:   Resolver casos con m = 1 como el Ejemplo 1.  5 Puntos 

• Test2:   Resolver casos con n ≤ 100.  15 Puntos 

• Test3:   Resolver casos con n ≤ 1000.  15 Puntos 

• Test4:   Resolver casos con n ≤ 10⁵.  15 Puntos 

• Test5:   Resolver casos de todo tipo.  50 Puntos