(Examen clasificatorio de la Olimpiada de Informática CDMX-EDOMEX ciclo 21-22 Nivel 02 Día 2 Problema 1)

Descripción

Durante su vida Luis Martín a coleccionado una cantidad ~N~ de discos de colores. El color de cada disco se representa por un número entero ~C_i~. Al reproducir cada uno de estos en un tocadiscos se va creando una melodía, los discos se reproducen en el orden conforme los fue coleccionando. Como Luis Martín es un experto en música sabe que una melodía solo es hermosa si tiene discos del mismo color. Como Luis Martín es una persona muy ordenada no le gustaría cambiar el orden en que se encuentran los discos, en cambio a él no le importaría eliminar algunos de los discos desde el inicio de su colección o desde el final de su colección.

A parte Luis Martín es un experto en conocimientos de química, por lo que ha desarrollado una poción que le permite cambiar el color de un disco por otro que el desee. Crear cada una de estas pociones le costará ~1~ nivel de experiencia. Luis Martín tiene ~K~ niveles de experiencia que ha recolectado durante toda su aventura, el podrá crear desde ~0~ hasta ~K~ pociones como máximo.

Problema

A Luis Martín le gustaría crear la melodía hermosa más larga posible con su colección de discos, y sus niveles de experiencia, ayúdalo a cumplir su tarea.

Entrada

En la primera línea dos números enteros ~N (1 \le N \le 10^6)~ y ~K (0≤ K < N ), la cantidad de discos de colores y los niveles de experiencia de Luis Martín.

En la segunda línea ~N~ enteros ~C_i~ ~(1\le C_i \le N )~ que representan el color de cada disco. Los colores de los discos se dan conforme Luis Martín los fue coleccionando.

Salida

Un solo número entero, la longitud de la melodía hermosa más larga que Luis Martín puede crear.

Ejemplo A

Entrada

10 6
2 2 4 5 6 7 8 9 2 2

Salida

10

Explicación.- La mejor solución para este caso sería de la posición ~3~ a la ~8~ utilizar pociones y cambiar todos los valores a ~2~. Los discos quedarían de la siguiente manera: 2, 2, 2, 2, 2, 2, 2, 2, 2 y 2. Entonces la melodía hermosa más larga seria de longitud ~10~, tomando todos los discos.

Ejemplo B

Entrada

7 0
2 3 3 4 4 5 5

Salida

2

Explicación.- Como se tienen ~0~ niveles de experiencia, no podemos cambiar ningún color de los discos, una de las soluciones posibles seria tomar los discos de la posición ~2~ a la ~3~.

Ejemplo C

Entrada

15 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Salida

2

Explicación.- Existen múltiples soluciones correctas, una de ellas seria cambiar el color del disco de la posición ~9~ por el color ~8~, y para la secuencia tomar los discos de la posición ~8~ a la ~9~.

Subtareas

Subtarea 1 con un valor de 5 puntos.
~K = N - 1~
Subtarea 2 con un valor de 30 puntos.
~N \le 100~.
Subtarea 3 con un valor de 30 puntos.
~N \le 1,000~.
Subtarea 4 con un valor de 20 puntos.
~N \le 10^5~.
Subtarea 5 con un valor de 15 puntos.
~N (1 \le N \le 10^6)~
~K (0\le K < N )~

NOTA:

Cada subtarea contiene un conjunto de casos de prueba, se te darán los puntos siempre y cuando tu programa resuelva todos los casos de la subtarea.