CF1614D2.Divan and Kostomuksha (hard version)

This is the hard version of the problem. The only difference is maximum value of $a_i$.

Once in Kostomuksha Divan found an array $a$ consisting of positive integers. Now he wants to reorder the elements of $a$ to maximize the value of the following function: $$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$ where $\operatorname{gcd}(x_1, x_2, \ldots, x_k)$ denotes the greatest common divisor of integers $x_1, x_2, \ldots, x_k$, and $\operatorname{gcd}(x) = x$ for any integer $x$.

Reordering elements of an array means changing the order of elements in the array arbitrary, or leaving the initial order.

Of course, Divan can solve this problem. However, he found it interesting, so he decided to share it with you.

这是该问题的困难版本。唯一的区别在于 $a_i$ 的最大值。

某日，科斯托穆克沙的迪万发现了一个由正整数组成的数组 $a$。现在他希望重新排列数组 $a$ 的元素，以最大化以下函数的值：

$$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$

其中 $\operatorname{gcd}(x_1, x_2, \ldots, x_k)$ 表示整数 $x_1, x_2, \ldots, x_k$ 的最大公约数，且对任意整数 $x$，定义 $\operatorname{gcd}(x) = x$。

对数组元素进行重排，是指以任意方式改变数组中元素的顺序，或保持原有顺序不变。

当然，迪万能够解决这个问题。然而，他觉得这个问题很有趣，因此决定与你分享。

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of the array $a$.

The second line contains $n$ integers $a_{1}, \, a_{2}, \, \dots, \, a_{n}$ ($1 \le a_{i} \le 2 \cdot 10^7$) — the array $a$.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_{1}, \, a_{2}, \, \dots, \, a_{n}$（$1 \le a_{i} \le 2 \cdot 10^7$）—— 数组 $a$。

Output the maximum value of the function that you can get by reordering elements of the array $a$.

输出通过重新排列数组 $a$ 的元素所能得到的函数的最大值。

In the first example, it's optimal to rearrange the elements of the given array in the following order: $[6, \, 2, \, 2, \, 2, \, 3, \, 1]$:

\\operatorname{gcd}(a\_1) + \\operatorname{gcd}(a\_1, \\, a\_2) + \\operatorname{gcd}(a\_1, \\, a\_2, \\, a\_3) + \\operatorname{gcd}(a\_1, \\, a\_2, \\, a\_3, \\, a\_4) + \\operatorname{gcd}(a\_1, \\, a\_2, \\, a\_3, \\, a\_4, \\, a\_5) + \\operatorname{gcd}(a\_1, \\, a\_2, \\, a\_3, \\, a\_4, \\, a\_5, \\, a\_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$ It can be shown that it is impossible to get a better answer. In the second example, it's optimal to rearrange the elements of a given array in the following order: $[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$. 在第一个例子中，将给定数组的元素按如下顺序重排是最优的：$[6, \, 2, \, 2, \, 2, \, 3, \, 1]$： $$\operatorname{gcd}(a\_1) + \operatorname{gcd}(a\_1, \, a\_2) + \operatorname{gcd}(a\_1, \, a\_2, \, a\_3) + \operatorname{gcd}(a\_1, \, a\_2, \, a\_3, \, a\_4) + \operatorname{gcd}(a\_1, \, a\_2, \, a\_3, \, a\_4, \, a\_5) + \operatorname{gcd}(a\_1, \, a\_2, \, a\_3, \, a\_4, \, a\_5, \, a\_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$ 可以证明无法得到更优的答案。 在第二个例子中，将给定数组的元素按如下顺序重排是最优的：$[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$。