Balanced Division for the Second Attack

In the new year, the long-awaited cat‐dog war takes a dramatic turn with a strategy inspired by the classic game StarCraft. Only the Terran faction and only building Marine units are allowed. After the first battle near the enemy’s base, some of the cat soldiers have been wounded and cannot be healed. Now, the cat army has regrouped and is ready to launch a second attack. To inflict maximum damage, the cats decide to split their current forces into two groups with the following rules:

• The number of soldiers in the two groups can differ by at most one.
• The total hit points (HP) of each group should be as nearly equal as possible.

You are given the number of soldiers and the HP value for each soldier. If the number of soldiers n is even, each group must have exactly n/2 soldiers; if n is odd, one group must have n//2 soldiers and the other must have n//2+1 soldiers. Determine the total HP for each of the two groups such that the absolute difference between the group sums is minimized. Output the two sums in ascending order.

inputFormat

The first line contains an integer n, the number of soldiers. The second line contains n space-separated positive integers representing the HP of each soldier.

outputFormat

Output two integers in ascending order separated by a space, representing the total HP of each group.

sample

3
1 2 3

3 3