Survival of the Weakest (hard version)
Contest: Codeforces Round 862 (Div. 2)
Difficulty rating: 3100
Tags: greedy, math, sortings, two pointers

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

Input format:
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 format:
Output a single number — the answer modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
5
1 2 4 5 6

Example output:
34

Example input:
9
1 1 1 7 7 7 9 9 9

Example output:
256

Editorial:
Firstly, we will sort the array $$$a_1, a_2, \ldots, a_n$$$, and in the future we will always assume that all arrays in this problem are sorted.
Let's solve the problem for $$$n \leq 200$$$.
It may seem that with such constraints, the problem is solved quite trivially: we implement the function $$$F$$$ for $$$\mathcal{O}(n^2 \log n)$$$, and run it $$$n - 1$$$ times to get an answer. But there is one nuance, with each iteration of $$$F$$$, the numbers in the array can increase by $$$2$$$ times (for example, if the array consists entirely of identical numbers), which means that after only $$$40$$$ operations, we may have an overflow. Note that it is impossible to take the numbers by modulo in the function $$$F$$$ itself, since then the sorted order will be lost, and it will be impossible (or very difficult) to restore it using the remainder when dividing by $$$10^9 + 7$$$ instead of the numbers themselves.
To avoid this, we note an important property of the function $$$F$$$:
$$$F([a_1, a_2, \ldots, a_n]) = F([a_1 - x, a_2 - x, \ldots, a_n - x]) + x \cdot 2^{n-1}$$$
The intuition of this property is that if you subtract the same number from all the elements, then the relative order of the elements will not change, and will not change when using the $$$F$$$ function. Just after the first iteration of $$$F$$$, $$$2x$$$ will be subtracted from all the numbers, then $$$4x$$$, $$$8x$$$, etc., in the end, the original answer will be minus $$$x\cdot 2^{n-1}$$$. This property can be proved more strictly by induction on $$$n$$$.
What does this wonderful property give us? Now we can subtract the same number $$$x$$$ from all the elements by first adding $$$x \cdot 2^{n-1}$$$ to the answer. It would be logical enough in any situation to subtract the minimum of the array from all its elements. Thanks to this, the minimum of the array will always be $$$0$$$, and now we can work only with arrays whose minimum element is $$$0$$$, which greatly simplifies our life. This is one of the two key ideas in this problem.
So let's notice something interesting about the array $$$F([0, a_1, a_2, \ldots, a_n])$$$.
Observation: $$$(F([0, a_1, a_2, \ldots, a_n]))_1 = a_1$$$. The proof is obvious (let me remind you that the array is sorted).
Observation: $$$(F([0, a_1, a_2, \ldots, a_n]))_n \leq a_n$$$.
Proof: since $$$[0, a_1, a_2, \ldots, a_n]$$$ has length $$$n + 1$$$, $$$F([0, a_1, a_2, \ldots, a_n])$$$ has length $$$n$$$. Among all pairs of array elements $$$[0, a_1, a_2, \ldots, a_n]$$$ there are $$$n$$$ pairs of the form $$$0 + a_i$$$, and $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$. This means that the original array has $$$n$$$ pairs in which the sum is $$$\leq a_n$$$. So, observation is proved.
These two observations give us that $$$F([0, a_1, a_2, \ldots, a_n]) = [a_1, \ldots, \leq a_n]$$$. And after subtracting the minimum $$$(a_1)$$$ $$$\rightarrow [0, \ldots, \leq a_n - a_1]$$$.
Thus, if we always subtract the minimum, each time after applying the $$$F$$$ function, the maximum in the array will be not increase. Which allows us to work only with arrays of numbers from $$$0$$$ to $$$10^9$$$, where there naturally can be no problems with overflow.
So, we got the solution for $$$\mathcal{O}(n^3 \log n)$$$. Let's improve it to $$$\mathcal{O}(n^2 \log n)$$$.
The cornerstone in our previous solution is that we implement the function $$$F$$$ for $$$\mathcal{O}(n^2 \log n)$$$, which is pretty slow. Let's learn how to implement it for $$$\mathcal{O}(n \log n)$$$. This is a fairly standard problem.
Note that if some pair of the form $$$a_i + a_j$$$ is included in the array $$$F([a_1, a_2, \ldots, a_n])$$$, then all pairs $$$a_i + a_{i+1}, a_i + a_{i+2}, \ldots, a_i + a_{j-1}$$$ will also be included in the array $$$F([a_1, a_2, \ldots, a_n])$$$, since the sum in these pairs is no more than $$$a_i + a_j$$$.
We will build the array $$$F([a_1, a_2, \ldots, a_n])$$$ one element at a time, starting with the smallest. Let's denote the array in which we will add these numbers for $$$B$$$, initially $$$B$$$ is empty. For each index $$$i$$$, we will store the minimum index $$$j_i > i$$$ such that the pair $$$a_i + a_j$$$ is still not taken in $$$B$$$. Initially, $$$j_i = i+1$$$.
We will mantain all numbers of the form $$$a_i + a_{j_i}$$$ in std::priority_queue. Then to add the next element to $$$B$$$, we will remove the minimum element from the queue, then increase the corresponding $$$j_i$$$ by one and add the element $$$a_i + a_{j_i}$$$ to the queue again. After $$$n - 1$$$ of such iteration we will get $$$F([a_1, a_2, \ldots, a_n])$$$. Each iteration takes $$$\mathcal{O}(\log n)$$$, which means that the asymptotics of finding the function $$$F$$$ is $$$\mathcal{O}(n \log n)$$$.
In total, we learned how to solve the problem in $$$\mathcal{O}(n^2 \log n)$$$.
Now we move on to the full solution, for $$$n \leq 2 \cdot 10^5$$$.
First we will show what the solution looks like and intuition behind it, and a more strict proof will be at the end.
Let's ask ourselves: when does the last element of the array $$$0, a_1, a_2, \ldots, a_n$$$ affect the answer to the problem?
Very often we will lose any mention of the $$$a_n$$$ element after the first transition: $$$[0, a_1, \ldots, a_n] \rightarrow F([0, a_1, \ldots, a_n])$$$.
The minimum sum of a pair of elements including $$$a_n$$$ is $$$0 + a_n$$$. And there is an $$$n - 1$$$ pair with not bigger sum: $$$0 + a_1$$$, $$$0 + a_2$$$, ..., $$$0 + a_{n-1}$$$.
So the only case when $$$a_n$$$ will enter the array $$$F([0, a_1, \ldots, a_n])$$$ is if $$$a_1 + a_2 \geq a_n$$$, because otherwise the pair $$$a_1 + a_2$$$ will be less than $$$0 + a_n$$$, and there will be $$$n$$$ pairs with a sum less than $$$a_n$$$ — $$$n-1$$$ pairs of the form $$$0 + a_i$$$ and the pair $$$a_1 + a_2$$$.
Well, let's assume it really happened that $$$a_1 + a_2 \geq a_n$$$. Then $$$F([0, a_1, \ldots, a_n]) = [0 + a_1, 0 + a_2, \ldots, 0 + a_n]$$$.
After subtracting the minimum: $$$[0, a_2 - a_1, a_3 - a_1, \ldots, a_n - a_1]$$$.
If we run $$$F$$$ on this array again, we get: $$$[a_2 - a_1, \ldots, \le a_n - a_1]$$$. After subtracting the minimum: $$$[0, \ldots, \le a_n - a_2]$$$.
But remember that $$$a_1 + a_2 \geq a_n$$$. Which means $$$2 \cdot a_2 \geq a_n$$$. Which means $$$a_n - a_2 \leq \frac{a_n}{2}$$$.
It turns out that if $$$a_n$$$ somehow remains in the array after two applications of the $$$F$$$ functions, then the last element of the array will be reduced by at least half!
This means that after just $$$2 \cdot \log_2{a_n}$$$ iterations of the $$$F$$$ function, either the $$$a_n$$$ element will be completely evicted from the array, or the array will shrink into $$$[0, 0, \ldots, 0]$$$! In both cases, the original element $$$a_n$$$ in no way will be taken into account in the final answer. In no way!
The total number of times when the maximum is halved is no more than $$$\log_2{a_n}$$$, which means intuitively it is approximately clear that elements with indexes greater than $$$2 \cdot \log_2{a_n}$$$ will not affect the answer in any way.
Therefore, the full solution would be to leave the first $$$K = 64$$$ elements of the array $$$a$$$. (a little more than $$$2 \cdot \log_2{10^9}$$$).
Then apply the function $$$F$$$ to this array $$$n - K$$$ times, but writing out $$$K$$$ minimal elements, not $$$K - 1$$$.
After that, the length of the real array will also be equal to $$$K$$$, and it remains only to run the function $$$F$$$ $$$K - 1$$$ times to get the final answer.
Final asymptotics: $$$\mathcal{O}(n \cdot (K \log K))$$$, where $$$K = 2 \log_2{a_n} + 2 \leq 64$$$.
Now let's give a strict proof that this solution works.
We are following $$$K$$$ minimal elements —$$$[0, a_1, \ldots, a_{K-1}]$$$.
Technically, there are also $$$[a_K, \ldots, a_{len}]$$$ elements in the array. But we have no information about their values. However, we know that all these elements are $$$\geq a_{K-1}$$$ since we maintain sorted order. This means that the minimum sum of a pair of elements about which we have no information is also $$$\geq a_{K-1}$$$. The whole proof is based on this simple observation.
Firstly, it is not difficult to understand that $$$K$$$ minimum elements are exactly enough to recalculate $$$K - 1$$$ minimum element in $$$F(a)$$$. Since we have pairs of elements $$$0 + a_1$$$, $$$0 + a_2$$$, ..., $$$0 + a_{K-1}$$$. And the sum in each of these pairs is no more than $$$a_{K-1}$$$, which means no more than the sum in any pair about which we have no information.
Therefore, in any incomprehensible situation, we can recalculate with the loss of one of the elements. Let's see when it is possible to recalculate all $$$K$$$ minimal elements.
Again, the minimum element about which we have no information from $$$[0, a_1, \ldots, a_{K-1}]$$$ is $$$0 + a_K \geq 0 + a_{K-1}$$$. So if we find $$$K$$$ elements that $$$\leq a_{K-1}$$$, then we can recalculate $$$K$$$ minimal elements of $$$F(a)$$$ through $$$K$$$ minimal elements of $$$a$$$. We have a $$$K - 1$$$ pair of the form $$$0 + a_i$$$, as well as a pair $$$a_1 + a_2$$$. So if $$$a_1 + a_2 < a_{K-1}$$$, then we can recalculate all $$$K$$$ minimal elements.
And if recalculation is not possible, then $$$a_1 + a_2 \geq a_{K-1}$$$ is executed. Then, having encountered such a situation, we will recalculate twice with the loss of the last element, thus reducing $$$K$$$ by $$$2$$$. After such a recalculation, the last element will be at least half as small as it was before (this is part of the main tutorial). So after $$$2 \log_2(A)$$$ of such element removals, the array will slide into $$$[0, 0, \ldots, 0]$$$ and everything is clear. And if the number of removals is less than $$$2 \log_2(A)$$$, then one of the $$$K$$$ elements will certainly live to the end, and will be the answer to the problem. Thus, the correctness of the solution has been successfully proved.
Bonus for those who are still alive: find a more accurate estimate for $$$K$$$ and build a test on which this solution, but keeping track of the $$$K - 1$$$ minimum element (one less than necessary), will give the wrong answer.