310256: CF1805F2. Survival of the Weakest (hard version)
Description
This is the hard version of the problem. It differs from the easy one only in constraints on $n$. You can make hacks only if you lock both versions.
Let $a_1, a_2, \ldots, a_n$ be an array of non-negative integers. Let $F(a_1, a_2, \ldots, a_n)$ be the sorted in the non-decreasing order array of $n - 1$ smallest numbers of the form $a_i + a_j$, where $1 \le i < j \le n$. In other words, $F(a_1, a_2, \ldots, a_n)$ is the sorted in the non-decreasing order array of $n - 1$ smallest sums of all possible pairs of elements of the array $a_1, a_2, \ldots, a_n$. For example, $F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$.
You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$. Determine the single element of the array $\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$. Since the answer can be quite large, output it modulo $10^9+7$.
InputThe first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the initial length of the array.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the array elements.
OutputOutput a single number — the answer modulo $10^9 + 7$.
ExamplesInput5 1 2 4 5 6Output
34Input
9 1 1 1 7 7 7 9 9 9Output
256Input
7 1 7 9 2 0 0 9Output
20Input
3 1000000000 1000000000 777Output
1540Note
In the first test, the array is transformed as follows: $[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$. The only element of the final array is $34$.
In the second test, $F(a_1, a_2, \ldots, a_n)$ is $[2, 2, 2, 8, 8, 8, 8, 8]$. This array is made up of $3$ numbers of the form $1 + 1$ and $5$ numbers of the form $1 + 7$.
In the fourth test, the array is transformed as follows: $[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$. $2 \cdot 10^9 + 1554$ modulo $10^9+7$ equals $1540$.
Input
题意翻译
给出序列 $a_{1\sim n}$，一次操作定义为将 $a$ 替换为 $a_i + a_j(i<j)$ 中的前 $(n-1)$ 小者，求进行 $(n-1)$ 次操作后的结果。对 $10^9+7$ 取模。Output
这是一个难题的困难版本，它与简单版本的区别仅在于对n的限制。只有当你锁定两个版本时，才能进行黑客攻击。给定一个非负整数数组a1，a2，…，an。定义F（a1，a2，…，an）为按非递减顺序排序的数组，其中包含n-1个最小的ai + aj形式的数，其中1≤i
输入输出数据格式：
输入：
第一行包含一个整数n（2≤n≤2*10^5）-数组的初始长度。
第二行包含n个整数a1，a2，…，an（0≤ai≤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题目大意： 这是一个难题的困难版本，它与简单版本的区别仅在于对n的限制。只有当你锁定两个版本时，才能进行黑客攻击。给定一个非负整数数组a1，a2，…，an。定义F（a1，a2，…，an）为按非递减顺序排序的数组，其中包含n-1个最小的ai + aj形式的数，其中1≤i