Taking Turns

Time limit1sMemory limit128 MB

Summary

Two players alternately take bales from a line, skipping any number of earlier bales; each plays optimally and takes the leftmost optimal bale. Find each player's total.

Level: Hard9 of 10
Topics: Dynamic programming, Greedy, Game theory, Implementation
Solved: No attempts yet

Problem

Farmer John has invented a new way of feeding his cows. He lays out $N$ ( $1 \le N \le 700000$ ) hay bales, numbered $1 \ldots N$ , in a long line in the barn. Hay bale $i$ has weight $W_i$ ( $1 \le W_i \le 2000000000$ ). A sequence of six weights might look like this:

17 5 9 10 3 8

A pair of cows named Bessie and Dessie walk down the line after examining every hay bale to learn its weight. Bessie chooses first. As they walk they take turns picking hay bales to eat; once a hay bale has been passed, it can never be picked again. For example, one possible walk down the line is:

Bessie picks the weight- $17$ bale.
Dessie skips the weight- $5$ bale and picks the weight- $9$ bale.
Bessie picks the weight- $10$ bale.
Dessie skips the weight- $3$ bale and picks the weight- $8$ bale.

Diagrammatically:

Bessie   |      |
        17 5 9 10 3 8
Dessie       |      |

This walk happens to skip only single bales, but on her turn a cow may skip as many bales as she likes.

Each cow wants to maximize the total weight of hay that she herself eats, and each knows the other has the same goal. Furthermore, whenever a cow has a choice, she eats the first (leftmost) bale that achieves her maximum possible total.

Given the sequence of hay weights, determine how much hay each cow eats as the pair goes down the line.

Input

Line $1$ : a single integer $N$ .
Lines $2 \ldots N+1$ : line $i+1$ contains a single integer $W_i$ .

Output

Line $1$ : two space-separated integers — the total weight of hay eaten by Bessie and by Dessie, respectively.

Examples3

Example 1
Input
```
6
17
5
9
10
3
8
```
Expected output
```
27 17
```
Example 2
Input
```
1
5
```
Expected output
```
5 0
```
Example 3
Input
```
2
10
20
```
Expected output
```
20 0
```