The longest divisible subsequence#264
Given a numeric sequence a_1, a_2, \dots, a_n, you need to find the length of the longest divisible subsequence.
A subsequence a_{k_1}, a_{k_2}, \dots, a_{k_t} (k_1 < k_2 < \dots < k_t) is called divisible if a_{k_i} \mid a_{k_j} for all 1 \leq i < j \leq t (the statement a \mid b means is divisible by ). A subsequence consisting of a single element is considered divisible by definition.
The first line contains a single natural number (1 \leq N \leq 1000) — the number of elements in the sequence. The next line contains integers, each with absolute value not exceeding 10^9, that form the sequence.
Output a single number — the required length.
Example 1