F2. Выживание слабейших (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Она отличается от простой только ограничением на $$$n$$$. Вы можете делать взломы, только если заблокируете обе версии задачи.

Пусть $$$a_1, a_2, \ldots, a_n$$$ — массив, состоящий из целых неотрицательных чисел. Определим $$$F(a_1, a_2, \ldots, a_n)$$$ как отсортированный по неубыванию массив, состоящий из $$$n - 1$$$ минимальных чисел вида $$$a_i + a_j$$$, где $$$1 \le i < j \le n$$$. Другими словами, $$$F(a_1, a_2, \ldots, a_n)$$$ — это отсортированный по неубыванию массив из $$$n - 1$$$ минимальных сумм всевозможных пар элементов массива $$$a_1, a_2, \ldots, a_n$$$. Например, $$$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$$$.

Вам дан массив, состоящий из целых неотрицательных чисел $$$a_1, a_2, \ldots, a_n$$$. Определите, чему равен единственный элемент массива $$$\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$$$. Так как ответ может быть достаточно большим, выведите его по модулю $$$10^9+7$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — начальную длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива.

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

Выведите единственное число — ответ на задачу по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
5
1 2 4 5 6
Выходные данные
34
Входные данные
9
1 1 1 7 7 7 9 9 9
Выходные данные
256
Входные данные
7
1 7 9 2 0 0 9
Выходные данные
20
Входные данные
3
1000000000 1000000000 777
Выходные данные
1540
Примечание

В первом тесте массив трансформируется следующим образом: $$$[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$$$. Единственный элемент конечного массива равен $$$34$$$.

Во втором тесте $$$F(a_1, a_2, \ldots, a_n)$$$ будет равен $$$[2, 2, 2, 8, 8, 8, 8, 8]$$$. Этот массив составлен из $$$3$$$ чисел вида $$$1 + 1$$$ и из $$$5$$$ чисел вида $$$1 + 7$$$.

В четвёртом тесте массив трансформируется следующим образом: $$$[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$$$. $$$2 \cdot 10^9 + 1554$$$ по модулю $$$10^9+7$$$ равняется $$$1540$$$.