Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP8_2G - Ciąg NWD

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;105] określająca liczbę elementów ciągu. W kolejnej linii znajduje się n liczb naturalnych z zakresu [1;105] będących elementami ciągu. Dla każdej pary sąsiadujących elementów zachodzi nierówność ai < ai + 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.


Dodane przez:Maciej Boniecki
Data dodania:2016-03-18
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Pochodzenie:VIII Mistrzostwa WWSI w Programowaniu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.