A15817. Survival of the Weakest (hard version)

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$ .

The 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.

Output a single number — the answer modulo $10^9 + 7$ .

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$ .