1688: 最长不互质序列

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：0

题目描述

现在有一个长度为 n 的序列，你需要从中选出一些数来，保持这些数在原来序列的相对
位置组成一个新的序列，使得相邻的两个元素不互质。输出新序列的最长长度。
两个数不互质，满足它们的最大公约数大于 1。

输入

第一行，一个整数 n，表示原序列的长度。
第二行，n 个数，表示序列中的元素。

输出

输出新序列的最长长度，数据保证答案至少为 2。

样例输入 复制 

7
2 3 4 5 6 7 8

样例输出 复制 

4

提示

【样例 1 解释】
最长不互质子序列为：2、4、6、8
【数据范围】
对于 20%的数据，所有输入数据的范围[1,20];
对于 40%的数据，所有输入数据的范围[1,10^3];
对于 70%的数据，所有输入数据的范围[1,10^5];
对于 100%的数据，所有输入数据的范围[1,10^6];