Bark Beetles

Two bark beetles have decided to devour an old wooden fence. The fence is a row of $n$ pickets whose heights are not necessarily equal. To make the meal more fun, the beetles turned it into a game and eat the pickets in alternating turns.

On its turn a beetle may either eat one of the two pickets currently at an end of the fence (the leftmost or the rightmost), or eat both end pickets at once. Each beetle always chooses so that the total height of the pickets it eats over the whole game is as large as possible.

The first beetle moves first. Determine how much wood each beetle ends up eating.

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of pickets.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), the heights of the pickets from left to right.

Print two integers on a single line: first the total height of the pickets eaten by the beetle that starts the game, then the total height eaten by its opponent.

Consider the fence $5\ 2\ 9\ 3$. On the first turn the starting beetle can take the picket of height $5$, the picket of height $3$, or both ends at once. Eating the picket of height $5$ is optimal: the opponent then faces $2\ 9\ 3$ and eats both ends ($2$ and $3$) at once, leaving $9$ for the starter. The starter eats $5+9=14$ and the opponent eats $2+3=5$.