Coin Game with Wallets

In this problem, there are n coins on a table, each with a face value. The coins are denoted by \(a_1, a_2, \cdots, a_n\) for the first, second, \(\ldots\) , nth coin respectively.

Bessie and Farmer John each have their own wallet, which is initially empty. They take turns picking coins from the table, with Bessie going first. In each turn, the current player performs the following:

• Let \(S\) be the total value of coins in the current player's wallet.
• If there exists at least one coin on the table whose value does not exceed \(S\) (i.e. \(a_i \le S\)), the player picks the coin with the maximum value among these.
• If every remaining coin has a face value greater than \(S\), the player picks the coin with the minimum value among all remaining coins.

The game ends when there are no coins left on the table. Your task is to determine the final total value of coins in Farmer John's and Bessie's wallets, respectively. Note that even though Bessie starts, the final output should list Farmer John's total first and then Bessie's.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 10^5)\), the number of coins.

The second line contains \(n\) integers \(a_1, a_2, \cdots, a_n\) \( (1 \le a_i \le 10^9)\) representing the face values of the coins.

outputFormat

Output two integers separated by a space: the total value in Farmer John's wallet and in Bessie's wallet, respectively.

sample

3
1 2 3

2 4