You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 现在有一个长度为 $n$ 的序列，他需要从中选出一些数来，保持这些数在原来序列的相对位置组成一个新的序列，并且使得相邻的两个元素不互质。小 Z 想要这样的新序列的长度最长，请你帮帮小 Z。

• 两个数不互质，即它们的最大公约数应该大于 $1$。

输入格式

第一行，一个整数 $n$，表示原序列的长度。

第二行，共 $n$ 个数，$a_1,a_2,\dots,a_n$，表示序列中的元素。

输出格式

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

样例 #1

样例输入 #1

7
2 3 4 5 6 7 8

样例输出 #1

4

提示

【样例解释】

我们可以选择序列 $\{2,4,6,8\}$ 作为新的序列，这个序列中相邻两个元素的公因数都为 $2$，满足条件。并且我们可以通过枚举每一个序列证明这个长度是最长的。

【数据范围】

对于 $20\%$ 的数据，所有输入数据的范围 $[1,20]$;

对于 $40\%$ 的数据，所有输入数据的范围 $[1,10^3]$;

对于 $70\%$ 的数据，所有输入数据的范围 $[1,10^5]$;

对于 $100\%$ 的数据，所有输入数据的范围 $[1,10^6]$。