c++ please

After acquiring a new integer and showing it off to other couples at a cocktail party, Alice and Bob headed home for a good night of sleep. As their integer was quite large, they were forced to carry it together. Then, on the Boole Boulevard, right by the Bayes Bay, disaster struck. History does not tell us which of our two protagonists stumbled first, but stumble they did, and their integer shattered into nn positive integral pieces on the pavement in front of them.

The couples marriage, already under financial stress due to the expensive integer acquisition, did not survive this event, and Bob and Alice resolved to separate. Thus the question was raised on how to split the remnants of their integer. Bob and Alice decided to play a game with the remaining nn pieces: the two would repeatedly choose pieces in alternating turns until none were left.

Bob and Alice, both very materialistic, seek to acquire the largest possible sum of integers possible. Compute the value of the integers each of them ends up with. Assume both players play optimally. Since A comes before B in the alphabet, Alice moves first.

Input

The input consists of two lines.

• A single integer 1n151n15, the number of pieces.

• The values of the pieces a0,a1,,an1a0,a1,,an1, space-separated. It is given that 1ai1001ai100.

Output

Output a single line containing two integers, the combined value of Alices pieces, and the combined value of Bobs pieces.

Output Output a single line containing two integers, the combined value of Alice's pieces, and the combined value of Bob's pieces. Sample Input 1 Sample Output 1 42 $ 3 3 1 2 Sample Input 2 Sample Output 2 33 1 2 2 1