Taking Turns

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.

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

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