Get Process Time

Assign each process in the original order. The core holding the lock can either give the current process to itself and hand over the lock, or give it to the other core and keep the lock; both sides maximize their own final total time, and core 1 initially holds the lock.

输入格式

The first line contains n, and the second line contains n values of time. The original bounds 1≤n≤100000 and 1≤time[i]≤10^9 are restored from Millennium's same-problem OCR001..004; the operation applies to the current i-th item, and the original Fastprep's i+1 is a typo. Output two exact integers.

输出格式

Output the total processing times of core 1 and core 2, one integer each.

样例 1

输入：

5
10 21 10 21 10

输出：

41 31

样例 2

输入：

4
10 10 10 10

输出：

20 20

样例 3

输入：

1
7

输出：

7 0

样例说明

The outputs of the three public examples are, in order: 41 31; 20 20; 7 0. Checked by independent enumeration or direct simulation.