ICPC公司计划构建一个由$$$n$$$服务器组成的集群计算系统。每个服务器都有一个 数据库协议类型 用正整数表示。具体来说,第$$$i$$$服务器具有协议类型$$$p_i$$$。
最初,所有服务器都是独立的。该公司希望在服务器之间建立连接,以便在最终的网络中,每台服务器都可以(直接或间接)到达其他服务器。
要实现完全连接,您可以建立多个连接。每次建立连接时,必须选择两个服务器$$$u$$$ 和$$$v$$$ ($$$u \lt v$$$)。在 $$$u$$$ 和 $$$v$$$ 之间建立连接的成本定义为 通用协议 $$$u$$$ 到 $$$v$$$ 范围内的数据库的 ,计算公式为 $$$\gcd(p_u, p_{u+1}, \ldots, p_v)$$$ $$$^{\text{*}}$$$。
确定完全连接所有 $$$n$$$ 服务器所需的最低总成本,以便每个服务器都可以从其他服务器访问。
示例输入 2 的插图。 $$$^{\text{*}}$$$$$$\mathrm{gcd}$$$ 是除该集合中的每个整数而不留下余数的最大正整数。
输入
第一行包含一个整数$$$n$$$,表示服务器的数量。
第二行包含$$$n$$$正整数$$$p_1, p_2, \ldots, p_n$$$,其中$$$p_i$$$是第$$$i$$$服务器的数据库协议类型。
- $$$2\leq n\leq 2\times 10^5$$$
- $$$1\leq p_i \leq 10^9$$$
输出
一行输出单个整数,代表完全连接集群计算系统所需的最小总成本。
示例
输入复制
3 4 2 6
输出复制
4
输入复制
6 2 4 6 7 14 21
输出复制
5
注意
例2说明: 该图显示了协议类型 $$$2$$$、$$$4$$$、$$$6$$$、$$$7$$$、$$$14$$$ 和 $$$21$$$ 的示例。所有可能连接的成本为 $$$1$$$、$$$2$$$ 或 $$$7$$$,由不同的宽度表示。有一种方法可以将所有连接连接在一起,每个连接的成本为 $$$1$$$(显示为红色)。