AT_abc469_f.GCD Maximum Spanning Tree

You are given a sequence of positive integers $A$ of length $N$.
There is a weighted complete undirected graph with $N$ vertices.
The vertices are numbered $1,2,\dots,N$.
For $i$ and $j$ satisfying $1 \leq i \lt j \leq N$, the weight of the edge connecting vertices $i$ and $j$ is the greatest common divisor of $A_i$ and $A_j$.
Find the maximum possible value of the sum of the weights of the edges included in a spanning tree of this graph.

给你一个长度为 $N$ 的正整数序列 $A$。
存在一个含 $N$ 个顶点的带权无向完全图。
顶点编号为 $1,2,\dots,N$。
对于满足 $1 \leq i \lt j \leq N$ 的 $i$ 和 $j$，连接顶点 $i$ 和 $j$ 的边的权重为 $A_i$ 与 $A_j$ 的最大公约数。
求该图的一棵生成树中所含边的权重之和的最大可能值。

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输入从标准输入中按以下格式给出：

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output the answer in one line.

一行输出答案。

Sample 1 Explanation:
The complete graph has the following three edges.

• The edge connecting vertices $1$ and $2$ with weight $2$
• The edge connecting vertices $1$ and $3$ with weight $4$
• The edge connecting vertices $2$ and $3$ with weight $6$

Choosing the second and third edges gives a sum of weights of $10$, which is the maximum possible value.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6$
• All input values are integers.

样例 1 解释：
该完全图包含以下三条边：

• 连接顶点 $1$ 和 $2$、权值为 $2$ 的边
• 连接顶点 $1$ 和 $3$、权值为 $4$ 的边
• 连接顶点 $2$ 和 $3$、权值为 $6$ 的边

选择第二条和第三条边，可得到权值之和为 $10$，这是可能的最大值。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6$
• 所有输入值均为整数。