005 - 最長の数列

問題

N個の正の整数を含む空でない集合S={x₁,x₂,…,x_N}が与えられます。
Sに対して、次の2つの性質をもつ長さM(≥1)の数列(a₁,a₂,…,a_M)を「良い」数列と言うことにします。

• 任意のi(1≤i≤M)に対してa_i∈S
• 任意のi(1≤i≤M−1)に対して、a_i < a_i+1 かつ a_i+1 は a_i の倍数

最も長い「良い」数列の長さを求めるプログラムを作成してください。

入力

N
x1 x2 ・・・ xN

1行目に1つの整数Nが与えられる。
2行目にスペース区切りでN個の整数x_iが半角空白区切りで与えられる。

• 1 ≦ N ≦ 10⁵
• 1 ≦ x_i ≦ 10⁶ (1 ≦ i ≦ N)
• xⁱ ≠ x^j (1 ≦ i ≦ j ≦ N)

出力

最も長い「良い」数列の長さを1行に出力してください。 最後に改行してください。

入出力例

入力例1

5
1 2 3 4 5

出力例1

3

解説

「良い」数列として、(1,2)や(2,4)や(5)などが考えられます。
長さが3の「良い」数列は(1,2,4)のみで、これが最大値です。

入力例2

7
3 4 8 9 16 27 432

出力例2

4

解説

長さが最大となる「良い」数列は(3,9,27,432)と(4,8,16,432)の2つあります。
「良い」数列の長さの最大を出力するので、4を出力します。

入力例3

7
1 2 22 88 8 4 440

出力例3

6

解説

x₁,x₂,・・・x_Nは昇順に並んでいないこともあります。

入力例4

5
2 3 5 7 11

出力例4

1