Coin Selection Game

Farmer John and Bessie are playing a coin selection game. Initially, there are \(n\) coins on the table with denominations \(a_1, a_2, \ldots, a_n\). Initially, both players' wallets are empty.

The players take turns starting with Farmer John. In each turn, the current player picks one coin from the table according to the following rules:

1. If there is at least one coin on the table with a denomination \(\leq\) the total denomination of the coins already in the player's wallet, the player picks the coin with the largest denomination among those.
2. If all coins on the table have denominations greater than the current total in the player's wallet, then the player picks the coin with the smallest denomination among those.

The picked coin is removed from the table and added to the player's wallet. The game ends when there are no coins left on the table. Your task is to compute the total denomination in Farmer John's wallet and Bessie's wallet at the end of the game.

inputFormat

The first line contains a single integer \(n\) (the number of coins). The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the denominations of the coins.

outputFormat

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

sample

3
1 2 3

4 2