Potato

Interview

Time limit1sMemory limit1024 MB

Summary

Park and Sungwoo take turns grabbing whole plates of fries, Park first, and the task is to find each player's total under optimal play.

Level: Easy2 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

Park, who loves french fries, is unlike Sungwoo, who does not like them that much. One day Park and Sungwoo receive a large pile of french fries and decide to split them.

There are $N$ plates on the desk. The $i$ -th plate has $a_i$ fries. Park and Sungwoo take turns doing the following.

Choose one plate that remains on the desk, and take the plate together with all the fries on it.

Repeat this until no plates remain on the desk. Park takes the first plate.

Park wants to maximize the number of fries he takes, and Sungwoo wants to minimize the number of fries he takes. Assuming both always play optimally, find the total number of fries that Sungwoo and Park each take in the end.

Input

The first line contains the number of plates $N$ . $(1 \leq N \leq 200\ 000)$

The second line contains the number of fries on each plate, $a_1, a_2, \cdots, a_N$ , separated by spaces. $(1 \leq a_i \leq 10\ 000)$

Output

On the first line, print the number of fries that Sungwoo takes and the number of fries that Park takes, separated by a space.

Hint

Park is Sungwoo's rival.

Examples3

Example 1
Input
```
2
10 4
```
Expected output
```
4 10
```
Example 2
Input
```
3
2 3 1
```
Expected output
```
1 5
```
Example 3
Input
```
6
2 2 3 3 4 4
```
Expected output
```
7 11
```