Fișierul intrare/ieșire	biochain.in, biochain.out	Sursă	Simulare OJI Clasa a 9-a
Autor	Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Biochain (clasa a 9-a)

În laboratoarele de cercetare genetică avansată, oamenii de știință analizează o nouă secvență de ADN sintetic. Această secvență este reprezentată ca un șir lung de valori numerice, numite “nucleotide sintetice”.

Stabilitatea moleculară a secvenței depinde de legăturile chimice dintre nucleotidele adiacente. Două nucleotide așezate pe poziții consecutive, având valorile A și B, formează o Legătură Stabilă dacă și numai dacă au “elemente comune” în structura lor internă. Matematic, acest lucru înseamnă că cele două numere nu sunt prime între ele (adică cmmdc(A,B)>1).

Un Bio-Lanț este o subsecvență continuă de nucleotide în care oricare două elemente vecine formează o Legătură Stabilă.

Cerință

Determinați lungimea maximă a unui Bio-Lanț din șir.

Date de intrare

Fișierul de intrare biochain.in conține pe prima linie numărul natural N, lungimea șirului. Pe cea de-a doua linie se află N numere naturale, valorile numerice din șir.

Date de ieșire

Fișierul de ieșire biochain.out va conține un singur număr natural, lungimea maximă a unui Bio-Lanț din sir.

Restricții

• 1 ≤ N ≤ 2.000.000
• 1 ≤ VAL ≤ 90.000
• Pentru 25% din teste, N ≤ 10.000.
• Pentru 50% din teste, N ≤ 400.000.
• Atenție! Se recomandă parsarea datelor de intrare!

Exemplu