Description

Farmer John lays out $n$ hay bales in a line, conveniently numbered $1..n$. Hay bale $i$ has weight $W_i$. The constraints are $1 \le n \le 7 \times 10^5$ and $1 \le W_i \le 2 \times 10^9$.

A sequence of six weights might look like: 17 5 9 10 3 8.

Two cows, Bessie and Dessie, walk down this line after examining all the hay bales and learning their weights. Bessie chooses first. They take turns picking hay bales to eat as they proceed from left to right. Either cow may skip any number of bales on her turn, but once a bale has been passed, neither cow can return to it, and each bale can be eaten at most once.

For example, as they go down the line, a possible scenario is:

• Bessie picks the 17-weight bale.
• Dessie skips the 5-weight bale and picks the 9-weight bale.
• Bessie picks the 10-weight bale.
• Dessie skips the 3-weight bale and picks the 8-weight bale. This scenario shows just one skipped bale; in general, either cow may skip any number of bales on her turn.

Each cow wishes to maximize the total weight of hay she herself consumes (and each knows the other has this goal). Furthermore, whenever multiple choices lead to the same maximum total for herself under optimal play, a cow will choose the first bale (the earliest position) among those optimal choices.

Given the sequence of hay weights, determine the total weight of hay eaten by Bessie and by Dessie, respectively.

Input Format

• Line 1: A single integer $n$.
• Lines $2..n+1$: Line $i+1$ contains a single integer $W_i$.

Output Format

• Line 1: Two space-separated integers: the total weight consumed by Bessie and by Dessie, respectively.

6 
17 
5 
9 
10 
3 
8 

27 17 

Hint

Translated by ChatGPT 5