Codeforces Round 862 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

math

sortings

two pointers

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
F2. Survival of the Weakest (hard version)

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis 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

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

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2024 11:14:11 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|