题目内容

小红在小红书从事用户行为分析工作。平台把每一次用户动作对应成正整数权值串 $\{w_1,w_2,...,w_m\}$，方便往后做关联推荐时把关键的“红色”动作抠出来。

被标出来的动作得有够用的共性，所以挑中的全部“红色”动作权值，其最大公约数必须比 $1$ 更大；另外，怕紧挨着的动作带来重复信息，挑中的位置下标不能紧挨。眼下给出该用户的一串动作记录，请问染成红色的动作最多能有几条。

[名词解释]

最大公约数:若干整数共同拥有的约数里那个最大者。比方说，$8、12$ 与 $20$ 的公共约数是 $1,2,4$ ，里头最大的那个是 $4$ ，所以 $gcd(8,12,20)=4$ 。

输入描述

首行读入整数 $m(1\le m\le 10^5)$ ,用来标明动作串有多长。

次行读入 $m$ 个整数 $w_1,w_2,\ldots,w_m(1\le w_k\le 100)$ ，用来标明各次动作的权值。

输出描述

于同一行打印一个整数，用来标明染红动作条数的上限。

样例1

输入

6
4 9 8 15 16 25

输出

3

说明

样例解释1

就本组数据而言，能把下标 $1$ 与 $3$ 与 $5$ 上的权值染红，三者最大公约数等于 $4$ ，并且互不紧挨，因而结果等于 $3$ 。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写