배수 부분수열

시간 제한2.5초메모리 제한256 MB

요약

수열이 주어질 때, 각 원소가 앞 원소의 더 큰 배수인 가장 긴 부분 수열의 길이를 구한다.

문제

자연수로 이루어진 수열이 주어진다. 이 수열의 부분수열 중에서 각 항이 바로 앞 항의 배수이면서 앞 항보다 큰 부분수열을 찾아, 그 최대 길이를 구한다.

부분수열은 원래 수열에서 항 몇 개를 순서를 바꾸지 않고 골라 만든다. 항이 하나뿐인 부분수열은 조건을 항상 만족하므로 답은 1보다 작아지지 않는다.

첫째 줄에 수열의 길이 $N$ ( $1 \le N \le 100000$ )이 주어진다.

다음 $N$ 개의 줄에 수열의 항이 순서대로 한 줄에 하나씩 주어진다. 각 항은 $1000000$ 보다 작은 자연수이다.

조건을 만족하는 가장 긴 부분수열의 길이를 첫째 줄에 출력한다.