该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，你可以在任意位置（即任意数字前后）插入一个你指定的数字。

请问最少添加多少次，才能使整个序列中，相邻两个元素均互质？

输入格式

输入共两行：第一行，一个正整数 $n$ ，第二行，$n$ 个正整数，表示给定序列$a_1,a_2,...,a_n$。

输出格式

输出共一行：一个整数，表示答案。

4
6 3 2 8

2

说明

最少添加两次，例如：在 $6$ 和 $3$ 之间插入一个 $5$，在$2$ 和 $8$ 之间插入一个 $3$。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 10$
• 对于 $60\%$ 的数据，$1\leq n\leq 10^3$，$1 \leq a_i \leq 10^3$
• 对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1 \leq a_i \leq 10^9$