Problema de competencia reciente que me gustó


#1

Hola, en el Educational Round 55 de CodeForces apareció el siguiente problema que me pareció lindo.

Link al problema original

Enunciado

Se tiene un arreglo a de largo n y un valor distinguido c. Se puede realizar una operación del siguiente tipo. Elegir un subarreglo [l,r] (1 \leq l \leq r \leq n), y un entero k (sin restricciones, puede ser positivo, negativo o cero). Una vez hecha esta elección, para cada l \leq i \leq r se cambia a_i := a_i+k.

¿Cuál es la máxima cantidad de índices que pueden quedar con valor c partiendo del arreglo original y realizando una operación descrita?

Entrada

La primera línea contiene dos enteros n y c \hspace{3pt}(1 \leq n \leq 5 \cdot 10^5, 1 \leq c \leq 5 \cdot 10^5), que son el largo del arreglo y el valor distinguido respectivamente.

La segunda línea contiene n enteros a_1,a_2, \dots, a_n \hspace{3pt}(1 \leq a_i \leq 5 \cdot 10^5), los enteros del arreglo a.

Salida

Se debe imprimir un entero con la máxima cantidad posible de elementos con valor c que se puede obtener luego de realizar una operación en el arreglo.

Entrada 1:

6 9
9 9 9 9 9 9

Salida 1:

6

Entrada 2:

3 2
6 2 6

Salida 2:

2

En el primer ejemplo se puede elegir cualquier subarreglo [l,r] y tomar k = 0, el arreglo no cambia y se obtiene la mayor cantidad de 9's posibles.

En el segundo ejemplo podemos elegir el subarreglo [1,3] y tomar k = -4, el arreglo resultante será [2,-2,2] que tiene la mayor cantidad de apariciones posibles del número c = 2.