CF264B Good Sequences

松鼠 Liss 对数列很感兴趣。她也有自己喜欢的整数。她认为 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ 是好的整数。 现在她感兴趣于好的数列。一个数列 $x_{1},x_{2},...,x_{k}$ 被称作“好”的当且仅当它满足以下三个条件： - 这个数列是严格递增的，即对每个 $i$ 满足 $1 \leq i \leq k-1$，都有 $x_{i} < x_{i+1}$。 - 任意相邻的两个元素都不是互质的，即对每个 $i$ 满足 $1 \leq i \leq k-1$，都有 $gcd(x_{i},x_{i+1}) > 1$（其中 $gcd(p, q)$ 表示整数 $p$ 和 $q$ 的最大公约数）。 - 数列中的所有元素都是好的整数。 请你求出最长好的数列的长度。

输入包含两行。 第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$）——好的整数的个数。 第二行包含 $n$ 个用空格分隔的整数 $a_{1},a_{2},...,a_{n}$，表示严格递增的好的整数（$1 \leq a_{i} \leq 10^{5};\ a_{i} < a_{i+1}$）。

输出一个整数，表示最长好的数列的长度。

在第一个样例中，以下这些数列都是好的数列的例子：$[2,\ 4,\ 6,\ 9]$，$[2,\ 4,\ 6]$，$[3,\ 9]$，$[6]$。最长的好的数列长度为 4。 由 ChatGPT 5 翻译