开始 2020-05-17 12:00:00

517编程5月月赛-普及组

结束 2020-05-17 14:30:00
Contest is over.
当前 2020-07-04 00:04:21

D. 良好的顺序

描述

良好序列是指序列单调递增且序列中相邻的两个数 GCD 大于1。

给你一个包含 $n$( $n<=1e5 $)个数的序列,求一个最长上升子序列且序列中相邻的两个数 GCD 大于1。保证输入的序列是递增的。

输入

输入由两行组成。

第一行包含一个整数 $n$($1\leq n\leq 10^5$)-整数的数量。

第二行包含一个以空格严格分隔的整数$a1,a2,...,an$的序列($1\leq ai\leq 10^5; ai <ai+1$)。 

输出

打印单个整数-最长的良好序列的长度。

样例

输入

5
2 3 4 6 9

输出

4

输入

9
1 2 3 5 6 7 8 9 10

输出

4

提示

对于30%的数据,$1\leq n\leq 10$;

对于60%的数据,$1\leq n\leq 100$;

对于100%的数据,$1\leq n\leq 10^5$;

时间限制 2 秒
内存限制 256 MB