ICPC 公司计划构建一个由 $n$ 台服务器组成的集群计算系统。每台服务器都有一个用正整数表示的数据库协议类型。具体来说，第 $i$ 台服务器的协议类型为 $p_i$。

最初，所有服务器都是独立的。公司希望在服务器之间建立连接，使得在最终的网络中，每台服务器都能到达其他所有服务器（直接或间接）。

为了实现完全连通，你可以建立若干连接。每次建立连接时，必须选择两台服务器 $u$ 和 $v$ ($u < v$)。建立 $u$ 和 $v$ 之间连接的代价定义为从 $u$ 到 $v$ 范围内所有数据库协议的公约数，即 $\gcd(p_u, p_{u+1}, \dots, p_v)^*$。

请确定将所有 $n$ 台服务器完全连通，使得每台服务器都能从其他所有服务器到达所需的最小总代价。

样例 2 的示意图。

输入格式

第一行包含一个整数 $n$，表示服务器的数量。 第二行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$，其中 $p_i$ 是第 $i$ 台服务器的数据库协议类型。

• $2 \le n \le 2 \times 10^5$
• $1 \le p_i \le 10^9$

输出格式

输出一行一个整数，表示将集群计算系统完全连通所需的最小总代价。

$^*$gcd 是指能整除该集合中每个整数的最大正整数。

样例

输入 1

3
4 2 6

输出 1

4

输入 2

6
2 4 6 7 14 21

输出 2

5

说明

样例 2 的解释：图中展示了一个协议类型分别为 2, 4, 6, 7, 14 和 21 的示例。所有可能连接的代价为 1, 2 或 7，由不同的宽度表示。有一种方法可以通过五个代价均为 1 的连接将所有服务器连通（图中以红色显示）。