给你一个由
个整数组成的数组
，现在你需要将数组划分出尽可能多的区间（假设划分为
段），每段区间需要满足：
每一段区间的长度都要
大于等于 
，我们使用
和
表示第
段区间的左右端点，需要满足
。
第一段区间的左端点必须为
，第
段区间的右端点必须为
；
对于第
)
段区间，满足
；
每段区间内的
每个数，都能够在当前区间中找到
至少一个除了自己之外的数字，与它
不互质；换句话来说，对于第
段区间的任意一个元素
)
，都至少存在一个
满足
、
，并且
%5Cne%201)
。
你只需要直接输出满足要求的最多段数，即
最大化 ，而不需要输出具体的划分方案。如果无法划分出满足要求的区间，则直接输出
。
输入描述:
第一行输入一个整数 )
代表数组中的元素数量。
第二行输入 
个整数 )
代表数组中的元素。
输出描述:
如果无法划分出满足要求的区间，则直接输出 
；否则，输出一个整数，代表满足要求的最多段数。
示例1
说明
在这个样例中，唯一满足条件的划分方案为：
。
示例2
说明
在这个样例中，唯一满足条件的划分方案为：
。
示例3
说明
由于区间长度必须大于等于 
，所以无法划分出满足要求的区间。