Company A is hosting an intellectual two-player game competition—the Stone Picking Game. The winner of the game will receive a generous prize provided by Company A, which has attracted many clever contestants from all over the country to participate.

Compared to the classic stone picking game, the rules for the game in Company A's competition are much more complex:

• There are a total of $N$ piles of stones arranged in a row, where the $i$-th pile contains $a_i$ stones.
• At the beginning, several piles of stones have already been intentionally removed by Company A.
• Then, two players take turns picking stones. In each turn, a player can take all the stones from one pile, but there is a constraint: a player can only take a pile if at least one of its adjacent piles has already been removed (either by a player in a previous turn or by Company A at the start). Note that the $1$-st pile is only adjacent to the $2$-nd pile, the $N$-th pile is only adjacent to the $N-1$-th pile, and any other $i$-th pile is adjacent to both the $i-1$-th and $i+1$-th piles.
• The game ends when all stones have been taken. The player who collects the most stones in total wins the game.

As one of the contestants in this competition, you are extremely clever and want to know, for any given game, the total number of stones the first player and the second player will each collect if both play with an optimal strategy.

Input

The first line of the input is a positive integer $N$, representing the number of piles of stones. The second line contains $N$ non-negative integers $a_1, a_2, \ldots, a_N$ separated by spaces, where $a_i$ represents the number of stones in the $i$-th pile, and $a_i=0$ indicates that the $i$-th pile was intentionally removed by Company A at the start. The input data guarantees $0 \le a_i \le 100{,}000{,}000$, and there is at least one $i$ such that $a_i=0$. For 30% of the data, $2 \le N \le 100$; for 100% of the data, $2 \le N \le 1{,}000{,}000$.

Output

Output a single line containing two integers, representing the total number of stones collected by the first player and the second player respectively when both use optimal strategies, separated by a space.

Examples

Input 1

8
1 2 0 3 7 4 0 9

Output 1

17 9

Note 1

When both players use optimal strategies, the order in which the stones are taken is $9, 2, 1, 4, 7, 3$. Therefore, the first player collects $9+1+7=17$ stones, and the second player collects $2+4+3=9$ stones.

Input 2

3
5 0 0

Output 2

5 0