UOJ Logo

NOI.AC

1S 512MB

#1645. 神奇序列

Statistics

题目描述

小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$