問題文
高桥是一位超级工程师。最近, 2 我们发明了一个名为“欧几里得”的机器人,它可以告诉你两个正整数的最大公约数。
为了测试Euclid的表现,高桥君 由N正整数组成的整数序列 A (1-索引)已准备好。
致欧几里得 A_i 和 在 A_{i+1} 的最大公约数 请他们了解 1 ≦ i ≦ N 。然而 A_{N+1} = A_1 。
欧几里得君 A_i 和 在 A_{i+1} 的最大公约数是 B_i 。
高桥君 B 似乎有一些不一致,所以我改变了整数序列 我决定根据 A 纠正它。但不幸的是整数序列 我丢失了 A 的数据。
这使得无法准确测量 Euclid 的性能。
然而,超级工程师高桥君创造的欧几里得君会报告很多错误的结果,这是令人难以置信的。
所以,高桥君 我们决定使用 B 中包含的尽可能少的虚假信息作为测量结果。 求
B 包含的虚假信息的最少数量。
入力
输入是从标准输入按以下格式给出的
N B_1 B_2 B_3 : B_N
- 1 在线 A 中的元素数量 来自行 N (1 ≦ N ≦ 10^5) 。 来自行
- 2 从线 N 行数过多 i 在线 B_i (1 ≦ B_i ≦ 10^9) 。 来自行
出力
Euclid 报告的虚假信息最少数量为 在 1 行输出。在输出末尾添加换行符。
入力例1
3 4 2 4
出力例1
1
B_1, B_3正确,则A_2 也是 因为它是 A_3 也是 因为它是 4 的倍数 B_2 ≧ 4 ,这是一个矛盾。 如果 B_2 是虚假信息,则不存在矛盾,所以答案是 删除 1 。
入力例2
10 3 1 4 1 5 9 2 6 5 3
出力例2
1
B_8可以消除矛盾。 可能A的一个例子是 [21, 39, 44, 28, 65, 45, 18, 34, 25, 15] 。
入力例3
10 2 7 1 8 2 8 1 8 2 8
出力例3
2