A chain is a sequence of positive integers A1, A2, A3, ..., An such that Ai+1 divides Ai. (In other words, A1 is a divisor of A2, A2 is a divisor of A3, and so on.)

The length of a chain is the number of elements in the sequence.

Given N elements, you need to find a chain of maximum length using a subset of the given elements.

1<=N<=1e6 1<=a[i]<=1e6

Now, you can sort the array and track gcd (LIS like approach), but how do you come up with a solution which adheres to the time limit?

N = 5 array = 4 2 5 80 4

ans = 4, i.e. [2,4,4,80]