問題文

長さ $N$ の整数列 $A = (A_1,\dots,A_N)$ が与えられます。
$A$ の連続とは限らない部分列 $(B_1,\dots,B_k)$ であって、 次の条件を満たすものの長さの最大値を求めてください。

• 任意の $1 \leq i \leq k-1$ に対して、$B_{i+1}$ は $B_i$ の倍数である。
  長さ $1$ の部分列は条件を常に満たすことに注意。

入力

$N$
$A_1$ $\dots$ $A_N$

• 入力は全て整数
• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^5$

出力

条件を満たす部分列の長さの最大値を出力してください。

サンプル

6
1 2 3 4 4 5

4

1
1

1

10
3 2 9 1 9 7 18 8 36 1

5