Balanced Partition of a Sequence

You are given a sequence of n integers. Your task is to partition the sequence into two subsequences, \(P_1\) and \(P_2\), such that:

• The absolute difference between the sums of \(P_1\) and \(P_2\) is minimized, i.e., \(|\sum P_1 - \sum P_2|\) is as small as possible.
• The maximum length of the two subsequences is minimized in the sense that the distribution of elements is as balanced as possible.

Note: For the purpose of this problem, a greedy algorithm that sorts the sequence in descending order and assigns each element to the subsequence with the smaller sum is acceptable.

inputFormat

The first line contains a single integer \(n\), the number of elements in the sequence.

The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

Output two lines:

• The first line contains the elements of the first subsequence \(P_1\) separated by spaces.
• The second line contains the elements of the second subsequence \(P_2\) separated by spaces.

## sample

5
1 2 3 4 5

5 2 1
4 3

</p>