题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，你可以在任意位置（即任意数字前后）插入一个你指定的数字。请问最少添加多少次，才能使整个序列中，相邻两个元素均互质？

输入格式

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

输出格式

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

4
6 3 2 8

2

样例解释 1

最少添加两次，例如：在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$