Problem Description

Farmer John and Bessie are playing a coin selection game together.

Initially, there are $n$ coins on the table, each with a denomination. We use $a_1, a_2, \cdots, a_n$ to represent the denominations of the 1st, 2nd, ..., nth coins respectively.

Both Farmer John and Bessie have their own wallets, which are initially empty.

Starting with Farmer John, they take turns in operations. In each operation, the current player selects the coin with the highest denomination that does not exceed the total denomination of the coins in their wallet from the remaining coins on the table. This coin is then taken from the table and placed into their wallet. If all remaining coins on the table have denominations greater than the total denomination of the coins in their wallet, then the player selects the coin with the smallest denomination.

The game ends when there are no coins left on the table.

Please calculate the total denomination of the coins in Farmer John's and Bessie's wallets after the game ends.

Input Format

The first line contains an integer, representing the initial number of coins on the table, $n$.
The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the denominations of the 1st, 2nd, ..., nth coins respectively.

Output Format

Output a single line containing two integers. The first integer represents the total denomination in Farmer John's wallet, and the second integer represents the total denomination in Bessie's wallet. Separate the two integers with a space.

Sample Input and Output

Sample Input #1

2
3 2

Sample Output #1

2 3

Sample Input #2

5
1 2 3 4 5

Sample Output #2

9 6

Notes

Sample 1 Explanation

When Farmer John starts, the total denomination in his wallet is $0$, which is less than any coin on the table, so he can only choose the coin with the smallest denomination, which is $2$.

Next, Bessie's wallet also has a total denomination of $0$, so she can only choose the coin with the smallest denomination, which is $3$.

Data Size and Constraints

• For $20\%$ of the data, $n \leq 2$.
• Another $20\%$ of the data guarantees $a_i = 1$.
• For $60\%$ of the data, $n \leq 100$.
• For $100\%$ of the data, $1 \leq n \leq 10^3$ and $1 \leq a_i \leq 10^{16}$.

见题面 Input 部分

见题面 Output 部分