#LX0022. 跳舞

跳舞

题目描述

小明在家打游戏,楼下在跳广场舞,吵死了。

nn个舞者排成一排,第ii个舞者的属性是aia_i

在每一刻,一个人可以邀请自己左侧或者右侧相邻的人跳舞,如果这两个人的属性的最大公约数>1>1,则这个人很开心,然后会开心回家睡觉。此时,他离开了跳舞的队列,他左右侧的两个人现在相邻了。

广场舞可太吵了,问:假设小明可以安排跳舞的顺序,最多能让多少个人回家睡觉!

输入格式

第一行输入nn

接下来一行输入nn个正整数表示aia_i

输出格式

一个数字表示答案。

样例输入 #1

5
1 6 3 2 4

样例输出 #1

3

样例解释 #1

33先跟22跳舞,跳完走人。让4422跳舞,跳完走人。让5522跳舞,跳完走人。

剩下俩人,分别属性是1,61,6,他俩去广场上站着吧。

样例输入 #2

6
6 2 3 4 15 9

样例输出 #2

5

数据范围

对于30%的数据:n20n\leq 20

对于70%的数据:n100n\leq 100

对于100%的数据:n500,1ai109n\leq 500,1\leq a_i\leq 10^9