Bark Beetles

Time limit1sMemory limit128 MB

Summary

Two beetles alternate taking one end picket or both end pickets from a row; each maximizes its own total, so find both final totals.

Level: Hard8 of 10
Topics: Dynamic programming, Game theory, Array, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Note

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$ .

Examples3

Example 1
Input
```
4
5 2 9 3
```
Expected output
```
14 5
```
Example 2
Input
```
2
7 4
```
Expected output
```
11 0
```
Example 3
Input
```
3
1 100 1
```
Expected output
```
2 100
```