Description

Xiao Ming's class is going to hold a tug-of-war competition. The homeroom teacher decides to divide everyone into two teams, and everyone must participate. The difference in the number of people between the two teams cannot exceed 1, and the total weight of the two teams should be as close as possible, with equality being the best case.

Input Format

The input contains multiple test cases.

For each test case, the first line is a positive integer n (2 ≤ n ≤ 100), indicating the number of people.

The next n lines each contain an integer w (1 ≤ w ≤ 450), representing the weight of each person.

Output Format

For each test case, output the total weights of the two teams in ascending order.

```input1 3 100 90 200 ``` ```output1 190 200 ``` ## Source

CodesOnline