WhiteRaptor finalmente ha encontrado a los de su propia especie en TheRaptorLand. A diferencia del WhiteRaptor común, TheRaptorLand tiene una variedad de raptores de colores: PinkRaptor, BlueRaptor y GreenRaptor.
WhiteRaptor alineó a todos los $n$ raptores en TheRaptorLand en una fila, numerados del 1 al $n$ de izquierda a derecha. El $i$-ésimo raptor desde la izquierda tiene el color $c[i]$. Él quiere elegir algunos raptores para que le hagan compañía en su sótano para siempre. Sin embargo, solo puede hacerlo eliminando cero o más raptores de los extremos izquierdo y derecho de la fila, y conservando todos los raptores que quedan.
Para asegurarse de que ninguno de los raptores que permanecen sea marginado, quiere que la diferencia entre la frecuencia del color de raptor más común y la frecuencia del color de raptor menos común no exceda $k$. Tenga en cuenta que si no queda ningún raptor de un color determinado, la frecuencia del color de raptor menos común será 0.
¡Ayude a WhiteRaptor a encontrar el número máximo de raptores que puede conservar!
Entrada
Su programa debe leer desde la entrada estándar.
La primera línea de la entrada contiene dos enteros $n$ y $k$.
La segunda línea de la entrada contiene $n$ enteros separados por espacios $c[1], c[2], \dots, c[n]$.
Salida
Su programa debe imprimir en la salida estándar.
Imprima un entero, el número máximo de raptores que puede conservar.
Subtareas
Para todos los casos de prueba, la entrada satisfará los siguientes límites:
- $1 \le n \le 200\,000$
- $0 \le k \le 200\,000$
- $1 \le c[i] \le 3$ para todo $1 \le i \le n$
Su programa será probado en instancias de entrada que satisfagan las siguientes restricciones:
| Subtarea | Puntuación | Restricciones adicionales |
|---|---|---|
| 0 | 0 | Casos de prueba de ejemplo |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | Existe un $1 \le j \le n$ tal que $c[i] \neq 3$ para todo $i \le j$, y $c[i] = 3$ para todo $i > j$ |
| 6 | 20 | En cualquier secuencia contigua de 3 o más raptores, el color 3 es el menos común |
| 7 | 24 | Sin restricciones adicionales |
Ejemplos
Entrada 1
11 2 2 2 1 2 1 3 2 1 2 1 1
Salida 1
7
Nota 1
Desde el raptor 3 hasta el raptor 9, el número de raptores con $c[i] = 1, 2$ y $3$ son 3, 3 y 1 respectivamente. Dado que la diferencia entre las frecuencias máxima y mínima no excede $k = 2$, este conjunto de raptores satisface el criterio de WhiteRaptor.
Un ejemplo de un conjunto inválido de raptores es desde el raptor 3 hasta el raptor 10, ya que la adición de otro raptor con $c[i] = 1$ hace que la frecuencia del color más común sea 4. La diferencia resultante entre las frecuencias máxima y mínima es 3, lo cual excede $k = 2$.
Se puede demostrar que 7 es el mayor número de raptores que WhiteRaptor puede conservar y que aún satisface su criterio.
Entrada 2
6 2 2 1 3 3 3 3
Salida 2
5
Nota 2
WhiteRaptor debería elegir los raptores desde el raptor 1 hasta el raptor 5.
Entrada 3
7 0 1 2 1 2 1 2 1
Salida 3
0
Nota 3
Dado que cualquier secuencia contigua de raptores no contendrá un raptor con $c[i] = 3$, la frecuencia del color menos común siempre será 0. Esto significa que WhiteRaptor no puede seleccionar ninguna secuencia no vacía de raptores. Por lo tanto, la salida es 0.