P7891 [Beginner Contest #10] Coin Selection G (hard version)

Farmer John and Bessie are playing a coin selection game together. At the beginning, there are $n$ coins on the table. Each coin has a face value. We use $a_1, a_2, \cdots, a_n$ to represent the values of coin $1, 2, \cdots, n$. They each have their own wallet, and both wallets are empty at the start. Starting from **Bessie**, they take turns. In each turn, the current player chooses, among the remaining coins on the table whose value is **not greater than the total value of coins currently in their own wallet**, the coin with the **largest** value, then takes it from the table and puts it into their wallet. If the values of **all** remaining coins on the table are **greater than the total value of coins already in their wallet**, then they choose the coin with the **smallest** value among all remaining coins. When there are no coins left on the table, the game ends. Please compute the total value of coins in Farmer John's wallet and in Bessie's wallet after the game ends.

The first line contains an integer $n$, representing the number of coins on the table initially. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the values of coins $1, 2, \cdots, n$.

Output one line with two integers. The first integer is the final total value of coins in Bessie's wallet, and the second integer is the final total value of coins in Farmer John's wallet.

### Constraints - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$ and $1 \le a_i \le 10^9$. Provider: 一扶苏一 Translated by ChatGPT 5