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 \le m \le k \le n \le 10^6$, 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.

• Test2:   Resolver casos con $n \le 100$.

• Test3:   Resolver casos con $n \le 1000$.

• Test4:   Resolver casos con $n \le 10^5$.

• Test5:   Resolver casos de todo tipo.