Для заданной числовой последовательности a[1]
, a[2]
, …, a[n]
требуется найти длину максимальной последовательнократной подпоследовательности.
Для последовательнократной подпоследовательности a[k1], a[k2], …, a[kt]
(k1 < k2 < … < kt
) верно, что a[ki] | a[kj]
при 1 <= i < j <= t
(утверждение a | b
эквивалентно b
кратно a
). Подпоследовательность из одного элемента полагается последовательнократной по определению.
В первой строке входного файла записано одно натуральное число N
(1 <= N <= 1000
) - количество чисел в исходной последовательности. Далее следует N
целых чисел, по модулю не превосходящих 10^9
- сама последовательность.
Вывести единственное число, равное искомому количеству.