Multiple Subsequence

Time limit2.5sMemory limit256 MB

Summary

Given a sequence, find the longest subsequence where each element is a larger multiple of the previous one.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting
Solved: No attempts yet

Problem

You are given a sequence of natural numbers. Find the length of the longest subsequence in which every element is a multiple of the element before it and strictly larger than it.

A subsequence is built by picking some elements of the original sequence without changing their order. A subsequence with one element always satisfies the condition, so the answer is never smaller than 1.

Input

The first line contains the length of the sequence $N$ ( $1 \le N \le 100000$ ).

Each of the next $N$ lines contains one element of the sequence, in order. Every element is a natural number smaller than $1000000$ .

Output

Print the length of the longest subsequence that satisfies the condition on the first line.

Examples2

Example 1
Input
```
5
1
2
3
4
5
```
Expected output
```
3
```
Example 2
Input
```
5
3
9
6
3
15
```
Expected output
```
2
```