#827 Don't Drop the Monkeys

Statement

Statement language

Monkeys are hanging from the floors of a tower with $H$ floors. The floors are numbered $1,2,\cdots,H$ from bottom to top. Initially, floor $i$ holds $a_i$ monkeys.

Ishigami and Iino take turns removing one remaining floor, with Ishigami moving first. All monkeys on the removed floor move to the highest remaining floor below it. If there is no such floor, the monkeys fall to the ground and the player who removed the floor collects them all. Monkeys that moved there on earlier turns follow the same rule.

A floor with no monkeys can also be removed. The game ends when all floors have been removed. The player with fewer monkeys wins; equal counts result in a draw. Both players play optimally to minimize the number of monkeys they collect. Find the numbers collected by Ishigami and Iino at the end of the game.

Input

The input is given in the following format:

$H$ $a_1\ a_2\ \cdots\ a_H$

Output

Print the numbers of monkeys collected by Ishigami and Iino, in this order, separated by a space.

Constraints

$1 \le H \le 1\,000\,000$ .
$0 \le a_i \le 10^9$ ().

Subtasks

#	Score	Constraints
1	100	No additional constraints.

Samples

Sample 1

Input

1
7

Output

7 0

Sample 2

Input

2
3 4

Output

0 7

Sample 3

Input

3
1 2 3

Output

6 0

Sample 4

Input

3
0 0 0

Output

0 0