e-olymp
Задачі

Найбільша послідовнократна підпослідовність

Найбільша послідовнократна підпослідовність

Для заданної числової послідовності a1, a2, …, an потрібно знайти довжину максимальної послідовнократної підпослідовності.

Для послідовнократної підпослідовності ak1, ak2, …, akt (k1 < k2 < … < kt) вірно, що aki | akj при 1 <= i < j <= t (твердження "a | b" еквівалентне "b кратне a"). Підпослідовність з одного елементу вважається послідовнократною за визначенням.

Вхіді дані

У першому рядку вхідного файлу задано одне натуральне число N (1 <= N <= 1000) - кількість чисел у заданій послідовності. Далі йде N цілих чисел, які за модулем не перевищують 109 - сама послідовність.

Вихідні дані

Вивести єдине число, рівне шуканій кількості.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
4
3 6 5 12
Вихідні дані
3