Two termites are eating an old wooden fence. This fence consists of $n$ planks of possibly different heights. Termites have already eaten some of them, and they thought that they should make their meal more interesting. They have decided to play a game and eat the planks in turns, one by one. During one turn, a termite may choose to eat only a plank which is next to a plank that has already been consumed.

Assuming that each termite chooses the planks in such a way, that during the whole game the sum of heights of all planks eaten by her is as big as possible, compute the amount of wood that each of them will have eaten.

Input Format

In the first line of the standard input there is an integer $n$ ($1 ≤ n ≤ 1\,000\,000$), denoting the number of planks in the fence. The second line contains a sequence of $n$ integers $l_{i}$ ($0 ≤ l_{i} ≤ 1\,000\,000\,000$), that describe the heights of the consecutive planks. If $l_{i} = 0$, then the corresponding plank has already been eaten. The plank number $i$ (for $1 < i < n$) is next to the planks number $i-1$ and $i+1$. The only plank adjacent to the plank number 1 is the plank number 2, and the only plank next to the plank number $n$ is the plank number $n-1$. At least one of $l_{i}$'s is equal to zero.

Output Format

You should write two integers to the first and only line of the standard output. The first integer should be the sum of the heights of the planks that will be consumed by the termite which starts the game, whereas the second one should be equal to the amount of wood that will go to his opponent.

Example

Input

8
1 2 0 3 7 4 0 9

Output

17 9

The fence consisted of 8 planks, out of which 2 have already been eaten. The first termite in his first turn can choose between planks of heights 2, 3, 4 and 9. During the optimal game, in the consecutive turns, termites will eat planks of heights 9, 2, 1, 4, 7 and 3.