問題文

長さ $N$ の数列 $A_0 \dots A_{N - 1}$ が与えられます。
その部分列 $ A_{i_0} \dots A_{i_{K - 1}}\ (0 \leq i_0 < \dots < i_{K - 1} < N) $ であって、

• 各項が次の項を割り切る： $ A_{i_0} | A_{i_1} | \dots | A_{i_{K - 1}} $
• 強単調増加である： $A_{i_0} < A_{i_1} < \dots < A_{i_{K - 1}}$

(21:43 $a_i$ を $A_i$ に修正)

入力

$N$
$A_0 \dots A_{N - 1}$

入力は全部で 2 行となり、以下の制約を満たします。

• 入力は全て整数
• $1 \leq N \leq 3 \times 10 ^ 5$
• $1 \leq A_i \leq 3 \times 10^5\ (0 \leq i < N)$

出力

条件を満たす部分列のうち最長なものの長さを一行で出力してください。

サンプル

5
2 4 6 1 8

3

5
1 3 3 9 2

3

1
1

1