Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

F2. Survival of the Weakest (hard version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 n1 smallest numbers of the form ai+aj, where 1i<jn. In other words, F(a1,a2,,an) is the sorted in the non-decreasing order array of n1 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(FFn1(a1,a2,,an))). Since the answer can be quite large, output it modulo 109+7.

Input

The first line contains one integer n (2n2105) — the initial length of the array.

The second line contains n integers a1,a2,,an (0ai109) — the array elements.

Output

Output a single number — the answer modulo 109+7.

Examples
Input
5
1 2 4 5 6
Output
34
Input
9
1 1 1 7 7 7 9 9 9
Output
256
Input
7
1 7 9 2 0 0 9
Output
20
Input
3
1000000000 1000000000 777
Output
1540
Note

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][2109+1554]. 2109+1554 modulo 109+7 equals 1540.