Joey and Jason are playing a stone game. There are piles of stones in a line, where the pile
has
(
) stones. The rules of this game are as follows:
- In each turn, a player must take a whole pile of stone.
- If a player wants to take one pile, one of the adjacent piles (neighbors) must be empty. Notice: since the
piles are placed in one line, pile
is only adjacent with pile
, pile
is adjacent with pile
and pile
, …, and pile
is only adjacent with pile
.
- When all piles are empty, the game is finished. The player who gets the most stones will be the winner.
Joey and Jason are both smart. So, they will always take the optimal strategy. Since Joey is younger than Jason, he will always go first. Could you please write a program to output the number of stones Joey and Jason will get?
Input Specification
The first line of input contains (
), the number of piles.
The second line of input contains non-negative integers,
(
), the number of stones in pile
. It is guaranteed that there is at least one pile of stone is empty at the beginning of the game.
Output Specification
Output the number of stones Joey and Jason will get in one line. It is guaranteed that the output does not exceed .
Sample Input
8
1 2 0 3 7 4 0 9
Sample Output
17 9
Explanation
Joey and Jason both take the optimal strategy, and they will take stones in the order 9, 2, 1, 4, 7, 3. Finally, Joey will get stones, while Jason will get
stones.
Comments
Why limit the languages?
Because this is CCO Preparation