题目描述

Kaguya 在家等 Iroha 回家。为了打发没有 Iroha 的无聊时光她决定玩一个数字游戏。

Kaguya 用月球黑科技给自己生成了含 $n$ 个数的序列 $a_1, a_2, \ldots,a_n$，她可以对这个序列执行 $0$ 次或任意多次以下操作：

• 选择数列里最大的数 $a_i$ 和最小的数 $a_j$，且不能选择同一个数（$i \neq j$），若 $a_i \bmod a_j = 0$，则将 $a_i$ 移出数列，否则将 $a_i$ 替换为 $a_i \bmod a_j$。

Kaguya 想知道要操作几次才能将数列的长度变为 $1$。她把这个问题发给了 Iroha，而 Iroha 在给她开发新身体没时间，于是把问题丢给了同在研究所工作的你。

可以证明无论怎么操作，操作次数总是固定的。

输入格式

输入第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，代表序列中的数。

输出格式

输出一行一个整数，代表需要的操作次数。

5
3 5 7 8 12

6

数据范围

• 对于 $60\%$ 的数据，$n \leq 1000$；
• 对于 $100\%$ 的数据，$2 \leq n \leq 2 \cdot 10^5$，$1 \leq a_i \leq 10^9$。