Adjacent-Zero Removal Game

Given a sequence of length \(n\): \(a = [a_1, a_2, \ldots, a_n]\), two players take turns. Initially, some elements of \(a\) are \(0\). In each turn, a player can choose any number \(a_i\) that is adjacent to a 0 (i.e. such that either \(a_{i-1} = 0\) or \(a_{i+1} = 0\), if such a neighbor exists), earn a score equal to its value, and then change \(a_i\) to \(0\). The game ends when no moves are available. Assuming both players play optimally, compute the final scores of the two players.

The rules can be summarized as follows:

• Initial input: an integer \(n\) followed by a sequence \(a_1,a_2,\ldots,a_n\).
• A move is valid if and only if the chosen element \(a_i\) (which is not 0) is adjacent to an element that is 0 (i.e. \(a_{i-1}=0\) or \(a_{i+1}=0\); the first and last elements need only one neighbor).
• After a move, the chosen element becomes 0.
• The players alternate moves, and if a player cannot move, the game ends.
• It can be shown that if both players use optimal strategies, a greedy simulation (always picking the maximum available move) yields the correct outcome.

Note: The existence of at least one 0 in the initial array is guaranteed so that there is at least one valid move at the start.

inputFormat

The first line contains an integer \(n\) (the length of the sequence).
The second line contains \(n\) space‐separated integers \(a_1,a_2,\ldots,a_n\).

outputFormat

Output two integers separated by a space: the final scores of the first player and the second player, respectively.

sample

3
0 5 1

5 1