401524: GYM100488 K Two Pirates

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 a_i 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.

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

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

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.

5
3 1 2 4 1

8 3

6
8 5 3 6 1 4

18 9