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

模运算谜题

题目描述

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

Kaguya 用月球黑科技给自己生成了含 $n$ 个数的序列 $a_1,a_2,\dots,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。可以证明无论怎么操作，操作次数总是固定的。

输入格式

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

输出格式

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

数据范围

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

样例数据

输入:

5
3 5 7 8 12

输出:

6