Maximize Sum of Processed Times

Tasks are assigned in order, and initially the first core holds the lock. The core holding the lock may either assign the current task to itself and hand over the lock, or assign it to the other core and keep the lock. Both sides maximize the total processing time they end up with; output the final payoffs of the first core and the second core.

输入格式

The input gives n and n task times. There are no original numeric bounds; this site adds 1≤n≤200000, 0≤time[i]≤10^9.

输出格式

Output the two integer payoffs, first core then second core, separated by a space.

样例 1

输入：

4
10 10 10 10

输出：

20 20

样例 2

输入：

5
10 15 20 25 30

输出：

55 45

样例 3

输入：

6
45 25 35 15 45 25

输出：

115 75

样例说明

The outputs of the three public examples are, in order: 20 20; 55 45; 115 75. They have been checked by independent enumeration or direct simulation.