Home

Contest: Task: Related: TaskE TaskG

Score : $2000$ points

Problem Statement

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.

Sample Input 1

5
20 100 10 1 10

Sample Output 1

120 21

If the two performs the optimal moves, the game proceeds as follows:

  • First, Sugim has to put his piece in the second box from the left.
  • Then, Sigma has to put his piece in the leftmost box.
  • Then, Sugim puts his piece in the third or fifth box.
  • Then, Sigma puts his piece in the fourth box.
  • Finally, Sugim puts his piece in the remaining box.

Sample Input 2

6
4 5 1 1 4 5

Sample Output 2

11 9

Sample Input 3

5
1 10 100 10 1

Sample Output 3

102 20