D2. Divan и Костомукша (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственным различием между версиями является ограничение на $$$a_i$$$.

Однажды в Костомукше Divan нашел массив $$$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$$$, а $$$\operatorname{gcd}(x) = x$$$ для всех целых чисел $$$x$$$.

Переупорядочить элементы массива означает каким-либо образом поменять порядок элементов в массиве или оставить исходный порядок.

Разумеется, Divan может решить эту задачу сам. Однако он посчитал, что она достаточно интересная, чтобы поделиться ею с вами.

Входные данные

В первой строке находится одно целое число $$$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$$$.

Выходные данные

Выведите максимальное значение функции, которое можно получить, переупорядочив элементы массива $$$a$$$.

Примеры
Входные данные
6
2 3 1 2 6 2
Выходные данные
14
Входные данные
10
5 7 10 3 1 10 100 3 42 54
Выходные данные
131
Примечание

В первом примере можно расположить элементы массива в следующем порядке: $$$[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]$$$.