Pracsiu Dan (dnprx) Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.
Cerința
Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.
Date de intrare
Fișierul de intrare cmmdcsecv.in conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.
Date de ieșire
Fișierul de ieșire cmmdcsecv.out va conține un singur număr natural reprezentând lungimea maximă a unei secvențe care are cel mai mare divizor comun strict mai mare decât 1.
Restricții și precizări
3 ≤ n ≤ 100.0001 ≤ ai≤ 1000, pentru orice1 ≤ i ≤ n
Exemplu:
cmmdcsecv.in
6 15 28 14 56 42 5
cmmdcsecv.out
4
Explicație
Secvența de lungime 4 este 28 14 56 42, deoarece cmmdc(28, 14, 56, 42) = 14 > 1. Nu există în șir o secvență de lungime mai mare care să îndeplinească cerința.