Codeforces Round 862 (Div. 2) |
---|
Finished |
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 a1,a2,…,an be an array of non-negative integers. Let F(a1,a2,…,an) be the sorted in the non-decreasing order array of n−1 smallest numbers of the form ai+aj, where 1≤i<j≤n. In other words, F(a1,a2,…,an) is the sorted in the non-decreasing order array of n−1 smallest sums of all possible pairs of elements of the array a1,a2,…,an. 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 a1,a2,…,an. Determine the single element of the array F(F(F…F⏟n−1(a1,a2,…,an)…)). Since the answer can be quite large, output it modulo 109+7.
The first line contains one integer n (2≤n≤2⋅105) — the initial length of the array.
The second line contains n integers a1,a2,…,an (0≤ai≤109) — the array elements.
Output a single number — the answer modulo 109+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
In the first test, the array is transformed as follows: [1,2,4,5,6]→[3,5,6,6]→[8,9,9]→[17,17]→[34]. The only element of the final array is 34.
In the second test, F(a1,a2,…,an) 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: [109,109,777]→[109+777,109+777]→[2⋅109+1554]. 2⋅109+1554 modulo 109+7 equals 1540.
Name |
---|