K. Two Pirates
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The famous pirate Jack Sparrow and not so famous pirate Ferrante Albrizzi, even less known as Malasorte, have robbed a Spanish trading schooner together and decided to divide the loot. The loot consists of n numbered items, the i-th of which costs ai piastres.

The pirates decided to take items in rotation. Jack Sparrow takes first because he is more famous. But Ferrante Albrizzi is not interested in money since he has become a pirate not because of them, so he just always takes the first item that hasn't been taken yet. Jack Sparrow perfectly knows it and wants to act to maximize the cost of his part of the loot. Determine how much piastres their loot will cost.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of items in the loot.

The second line contains n integers separated by spaces: ai (1 ≤ ai ≤ 109) — the cost of the i-th item.

Output

Output in the only line two integers separated by a space: the cost of loot taken by Jack Sparrow and the cost of loot taken by Ferrante Albrizzi.

Examples
Input
5
3 1 2 4 1
Output
8 3
Input
6
8 5 3 6 1 4
Output
18 9