B'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 <= i < j <= 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 <= n <= 2 cdot 10^5 ) -- the initial length of the array. The second line contains n integers a_1, a_2, ldots, a_n ( 0 <= a_i <= 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 . '...