POLSKI SPOJ

Dany jest ciąg rosnący n liczb naturalnych. Twoim zadaniem jest wyznaczenie długości najdłuższego podciągu, w którym największy wspólny dzielnik każdej pary sąsiadujących elementów jest większy od 1.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1;10⁵] określająca liczbę elementów ciągu. W kolejnej linii znajduje się n liczb naturalnych z zakresu [1;10⁵] będących elementami ciągu. Dla każdej pary sąsiadujących elementów zachodzi nierówność a_i < a_{i + 1}.

Wyjście

Na wyjściu należy wypisać długość szukanego podciągu.

Przykład

Wejście

9
2 5 6 7 8 12 15 19 20

Wyjście

6

Wyjaśnienie do przykładu

Najdłuższy podciąg spełniający warunek to: 2, 6, 8, 12, 15, 20. Największe wspólne dzielniki kolejnych par sąsiadujących elementów to: 2, 2, 4, 3, 5.