|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
D - Cadena de números
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Fito está estudiando Teoría de Números y encuentra muy interesante el concepto de divisor común. Por ejemplo le sorprende que el máximo común divisor de dos números sea una combinación lineal de estos. También ha estudiado cadenas de números con divisores comunes y quiere construir una con la mayor cantidad de números posibles.
Para hacer esto Fito tiene una lista con muchos enteros y con ellos va a formar una cadena de números en orden estrictamente creciente. Para todo par de números consecutivos se debe cumplir que existe un divisor común entre ellos mayor que uno.
Input
La primera línea de la entrada es un entero $N (1 ≤ N ≤ 10^5)$ la cantidad de números que tiene la lista de Fito. La segunda línea contiene $N$ enteros separados por un espacio en orden estrictamente creciente. Todos los números de la lista están entre $1$ y $10^5$.
Output
La salida es un entero con la longitud de la mayor cadena que puede formar Fito.
Sample test(s)
Input
4
2 4 5 6
Output
3