题目描述
小A同学发明了一种神奇序列,这种序列的定义是,一个正整数序列,其中任意两个相邻元素都不互质(即拥有1以外的公因子),现在小A获得了一个正整数序列,他希望能找到该序列中最长的一个子序列,并使其为一个神奇序列。
文件输入
第一行一个正整数n,表示序列的长度 接下来一行n个正整数,分别表示序列的n个元素,序列的第i个元素为$a_i$
文件输出
输出给定的序列中能找到的最长的神奇序列长度
输入样例
5
2 2 2 2 2
输出样例
5
数据规模
对于前20%的数据,$n<=100$,$a_i \le 1000$ 对于前40%的数据,$n<=1000$,$a_i \le 10000$ 对于前60%的数据,$n<=5000$,$ai \le 100000$ 对于前100%的数据,$n<=100000$,$ai \le 1000000$