Balanced Box Arrangement

You are given N boxes with corresponding weights. Your task is to rearrange the weights in such a way that when the boxes are divided into two halves (the first half and the second half), the difference between the total weight of the two halves is minimized.

The official condition for balance is that the absolute difference between the sum of the weights in the two halves should be at most
$$ \left|\sum_{i \in left} w_i - \sum_{j \in right} w_j\right| \leq \max(weights). $$

One common approach is to sort the weights in descending order and assign each weight to the side with the smaller sum, resulting in a reasonably balanced configuration. Note that the arrangement is not necessarily unique. In this problem, implement the algorithm described above.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer N denoting the number of weights.
• The second line contains N space-separated integers representing the weights.

outputFormat

Output a single line to standard output (stdout) containing N space-separated integers. The integers represent the weights arranged according to the balancing strategy.

4
4 5 6 5

6 4 5 5