题目描述

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

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

为了实现完全连通，可以建立若干条连接。每次建立连接时，必须选择两台服务器 $u$ 和 $v$（$u < v$）。连接 $u$ 和 $v$ 的费用定义为从 $u$ 到 $v$ 范围内服务器协议类型的最大公约数，即 $\gcd(p_u, p_{u+1}, \ldots, p_v)$。

请你计算，为了让所有 $n$ 台服务器都能够互相连通，所需的最小总代价是多少。

输入描述

第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示服务器的数量。

第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le 10^9$），其中 $p_i$ 表示第 $i$ 台服务器的协议类型。

输出描述

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

样例

样例 1

3
4 2 6

4

样例 2

6
2 4 6 7 14 21

5

注释

对于第二组测试用例，图中节点的协议类型分别为 $2, 4, 6, 7, 14, 21$。所有可能的连接费用为 $1, 2$ 或 $7$。存在一种连接方式，通过五条费用为 $1$ 的连接，就能将所有服务器连接起来。