Problema B - Enormes Olas
Cuando no está estudiando algoritmos o programando estructuras de datos muy complejas, a Rafael le gusta surfear en las arenosas playas de su ciudad natal. Es realmente muy bueno (tal vez debería focalizarse más en la programación) y disfruta participar de competencias y eventos de surf. Le gustan especialmente las olas gigantes, que lo hacen sentir en paz consigo mismo mientras surfea y siente el océano.
Una ola se puede ver como una secuencia de enteros (estos enteros tienen que ver con complicadas fórmulas del surf y podemos simplemente asumir que serán dados). Hay dos conceptos muy importantes relacionados con las olas: longitud y magnitud. La longitud de una ola es el número de enteros en la secuencia. La magnitud de una ola se define como el máximo común divisor (mcd) de todos los números en la secuencia. Definimos máximo común divisor de un conjunto de enteros como el mayor entero positivo que divide a los números sin dejar resto. Por ejemplo, gcd(8,20) = 4, y gcd(15,5)=5
Rafael va a participar en el campeonato mundial del surfeo de la ola más grande. Afortunadamente, sabe exactamente cómo estará el agua durante el evento. Esto está dado por una secuencia de N enteros. Cualquier subsecuencia (intervalo contiguo de enteros) de esta secuencia es una ola. Como Rafael no puede surfear todas las olas, necesita encontrar la ola más larga para surfear. Sin embargo, hay un mínimo de magnitud de ola requerido, para asegurarse de que no pueda simplemente elegir toda la secuencia. Considerando, por ejemplo, que N=5, M=2 y que nos es dada la siguiente secuencia:
3 2 4 6 5
La mayor ola que tiene magntitud mínima 2 es la ola {2,4,6}, con longitud 3. Notar que mcd(2,4,6)=2, y luego esta ola tiene magnitud 2. Cualquier otra ola posible sería o bien más corta (una subsecuencia de menos de 3 enteros) o tendría una magnitud menor que lo que es requerido (por ejemplo, la ola {3,2,4,6,5} tiene magnitud 1).
¿Puedes ayudar a Rafael a encontrar la mayor ola que pueda surfear para que gane el campeonato?
El Problema
Dados dos enteros N y M y una secuencia de N enteros, representando la condición del agua, debes calcular la ola más larga con magnitud mínima M, esto es, la más larga subsecuencia de números contiguos para los que su máximo común divisor es mayor o igual a M.
Datos de entrada
La primera línea contiene dos enteros N (longitud de la secuencia de enteros dada) y M (magnitud mínima de una ola para ser considerada), separados por un único espacio.
La segunda línea contiene una secuencia que representa la condición del agua. Esto está dado por una secuencia de N enteros Vi, separados por un solo espacio, donde Vi es el i-ésimo entero de la secuencia.
Datos de salida
Una sola línea, conteniendo un entero que representa la longitud de la mayor ola que tiene magnitud mínima M.
Restricciones
Los siguientes límites son garantizados para todos los casos de prueba que sean usados para evaluar tu programa:



1 ≤ N ≤ 500 000
     
Número de enteros en la secuencia


1 ≤ M ≤ 230
     
Magnitud mínima de la ola


1 ≤ Vi ≤ 230
     
Máximo valor para un entero de la secuencia



Nota acerca de la evaluación
Para el conjunto de casos de prueba que valen el 25% de los puntos, siempre ocurre que N≤ 100.
Para el conjunto de casos de prueba que valen el 60% de los puntos, siempre ocurre que N≤5 000.




Entrada ejemplo 1
5 3
3 6 8 9 3

Salida ejemplo 1
2
Explicación de la entrada 1
Ambos {3,6} y {9,3} tienen magnitud 3. Todas las olas que incluyan el número 8 tendrán magnitud menor que 3 y luego la ola más larga que respeta la magnitud mínima requerida tiene longitud 2.

 

Entrada ejemplo 2
10 2
3 5 10 25 2 13 2 4 1 2
Salida ejemplo 2
3
Explicación de la entrada 2
La secuencia {5,10,25} tiene longitud 3 y magnitud 5. Como no hay una secuencia más larga con magnitud mayor o igual a 2, la ola más larga con la magnitud mínima requerida tiene longitud 3.