0584 - 最長の数列

時間制限 1 秒 / メモリ制限 256 MB / 得点 1 / Writer ei1428 / x 8 / 統計 /

    タグ:
  • DP

TLE
1sec
MLE
256MB
得点
1

問題

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

  • 任意のi(1≤i≤M)に対してai∈S
  • 任意のi(1≤i≤M−1)に対して、ai < ai+1 かつ ai+1 は ai の倍数
最も長い「良い」数列の長さを求めるプログラムを作成してください。

入力

N
x1 x2 ・・・ xN

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

  • 1 ≦ N ≦ 105
  • 1 ≦ xi ≦ 106 (1 ≦ i ≦ N)
  • xi ≠ xj (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

解説

x1,x2,・・・xNは昇順に並んでいないこともあります。

入力例4

5
2 3 5 7 11

出力例4

1