题目描述

小 C 非常喜欢数字。

这次，他得到了一个长度为 $n$ 的正整数数列 $A$，第 $i$ 项为 $a_i$。

现在，小 C 想要找出来 $A$ 中 最长的子序列 $B = \{b_1, b_2, · · · , b_m\}$，使得对于 任意 的二元组 $(i, j)$，$b_i$ 和 $b_j$ 满足 倍数关系。 小 C 突然不会最长不下降子序列了，于是找到了你来帮他求出最长的子序列的长度。

子序列：对于长度为 $n$ 的数列 $A$，对于 $B = \{b_1, b_2, · · · , b_m\}$，若 $b_1 = a_{p_1}, b_2 = a_{p_2} , · · · , b_m = a_{p_m}$，则必须要满足 $1 ≤ p_1 < p_2 < · · · < p_m ≤ n$，这样的数列 $B$ 称为 $A$ 的子序列。其中子序列 $B$ 可以为空。

倍数关系：对于两个数 $a, b$，两者成倍数关系，即 $a$ 能被 $b$ 整除，或者 $b$ 能被 $a$ 整除，两者至少一种成立。

输入格式

从文件 number.in 中读取数据。

共两行，第一行有一个正整数 $n$，表示数列 $A$ 的长度；

第二行有 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

输出格式

输出到文件 number.out 中。

仅一行一个数，表示子序列长度的最大值。

样例

5
1 2 3 8 16

4

解释#1

最长子序列为 $\{1, 2, 8, 16\}$，长度为 $4$。

10
1 4 6 3 9 11 16 24 42 36

4

解释#2

最长长度为 $4$，选取方案不唯一，其中一种最长的子序列为 $\{1, 6, 3, 24\}$。

样例3

见选手目录下的 number/number3.in 和 number/number3.ans。

数据范围

对于所有数据：$0 < N ≤ 3 × 10^6，0 < a_i ≤ 10^7$。

如有需要，请使用scanf读入以及减少使用STL，以降低程序本身带来的常数。