Manju Game

There are N boxes arranged in a row from left to right. The i-th box from the left contains a_i manju (buns stuffed with bean paste). Sugim and Sigma play a game using these boxes. They alternately perform the following operation. Sugim goes first, and the game ends when a total of N operations are performed.

• Choose a box that still does not contain a piece and is adjacent to the box chosen in the other player's last operation, then put a piece in that box. If there are multiple such boxes, any of them can be chosen.
• If there is no box that satisfies the condition above, or this is Sugim's first operation, choose any one box that still does not contain a piece, then put a piece in that box.

At the end of the game, each player can have the manju in the boxes in which he put his pieces. They love manju, and each of them is wise enough to perform the optimal moves in order to have the maximum number of manju at the end of the game.

Find the number of manju that each player will have at the end of the game.

Constraints

• 2 \leq N \leq 300 000
• 1 \leq a_i \leq 1000
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N a_1 a_2 ... a_N

Output

Print the numbers of Sugim's manju and Sigma's manju at the end of the game, in this order, with a space in between.

Examples

Input

5 20 100 10 1 10

Output

120 21

Input

6 4 5 1 1 4 5

Output

11 9

Input

5 1 10 100 10 1

Output

102 20

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N a_1 a_2 ... a_N

outputFormat

Output

Print the numbers of Sugim's manju and Sigma's manju at the end of the game, in this order, with a space in between.

Examples

Input

5 20 100 10 1 10

Output

120 21

Input

6 4 5 1 1 4 5

Output

11 9

Input

5 1 10 100 10 1

Output

102 20

样例

5
20 100 10 1 10

120 21