问题文

高桥君是一位超级工程师。最近，他发明了一个名为"欧几里得君"的机器人，可以告诉他两个正整数的最大公约数。

为了测试欧几里得君的性能，高桥君准备了一个由N个正整数组成的整数序列A（从1开始索引）。

他让欧几里得君求得Ai和Ai+1的最大公约数，其中1≤i≤N。注意，AN+1=A1。

欧几里得君报告给他的结果是Bi，即Ai和Ai+1的最大公约数。

高桥君觉得Bi中可能存在一些矛盾，所以他想根据整数序列A进行修改。然而，不幸的是，他丢失了整数序列A的数据。

这样一来，他就无法正确地评估欧几里得君的性能了。

然而，作为一位超级工程师，高桥君制作的欧几里得君不太可能报告出错的次数很多。

因此，高桥君决定将B中包含的错误信息数量中的最小值作为测量结果。

请计算B中包含的错误信息数量的最小值。

输入

输入通过标准输入给出，具体格式如下：

N B1 B2 B3 ... BN

• 第1行为整数N，表示序列A的元素个数（满足1≤N≤10^5）；
• 第2行至第N行每行包含一个整数Bi，表示欧几里得君报告的结果。

输出

请输出欧几里得君报告的错误信息数量的最小值，输出末尾需要换行。

示例输入1

3
4
2
4

示例输出1

1

如果假设B1和B3是正确的，那么A2和A3都是4的倍数，所以B2≥4，与之前的结果矛盾。如果B2是错误的，就不存在矛盾了，所以答案是1。

示例输入2

10
3
1
4
1
5
9
2
6
5
3

示例输出2

1

如果将B8移除，就不会有矛盾了。可以考虑的一个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