← 返回题目列表

Codeforces · 264/B

B. 好的序列

中文机器翻译题面 查看原题

Squirrel Liss 对序列感兴趣。她也对整数有偏好。她认为n个整数a1,a2,...,an是好的。

现在她对好的序列感兴趣。如果序列 x1, x2, ..., xk 满足以下三个条件,则称为良好序列:

- 序列严格递增,即对于每个 i,xi < xi + 1 (1 ≤ i ≤ k - 1)。
- 没有两个相邻元素互质,即对于每个 i (1 ≤ i ≤ k - 1),gcd(xi, xi + 1) > 1(其中 gcd(p, q) 表示整数 p 和 q 的最大公约数)。
- 序列中的所有元素都是好整数。

找到最长的好序列的长度。

输入

输入由两行组成。第一行包含一个整数 n (1 ≤ n ≤ 105) — 好整数的数量。第二行包含一个以单空格分隔的好整数 a1、a2、...、an 列表,按严格递增顺序 (1 ≤ ai ≤ 105;ai < ai + 1)。

输出

打印一个整数——最长的好序列的长度。

示例

输入 #1

5
2 3 4 6 9

输出 #1

4

输入 #2

9
1 2 3 5 6 7 8 9 10

输出 #2

4

注意

在第一个示例中,以下序列是良好序列的示例:[2; 4; 6; 9],[2; 4; 6],[3; 9],[6]。最长的好序列的长度是4。