Longest Divisible Subsequence

You are given a sequence of integers. A subsequence is called divisible if every element (except the first) is divisible by its immediate predecessor. Your task is to determine the length of the longest divisible subsequence that can be formed from the given sequence.

Note: The subsequence does not need to be contiguous in the original sequence. However, you are allowed to reorder the sequence (by sorting) to find the longest chain where for any two consecutive elements \(a\) and \(b\), \(b \bmod a = 0\). The solution should work for any input sequence.

inputFormat

The first line contains an integer \(N\), the number of elements in the sequence. The second line contains \(N\) space-separated integers representing the sequence.

outputFormat

Output a single integer—the length of the longest divisible subsequence.

4
3 6 18 36

4