Split List for Minimum Sum Difference

You are given a list of n integers. Your task is to split this list into two non-empty sublists such that the absolute difference between the sums of the two sublists is minimized. In mathematical terms, if you partition the list into sublists S₁ and S₂, you need to minimize the expression \[ \left|\sum_{a\in S_1}a - \sum_{a\in S_2}a\right| \]

For example, for the input list [1, 2, 3, 4, 5], one valid partition is [1, 2, 4] and [3, 5] where the difference is |(1+2+4) - (3+5)| = |7-8| = 1. Note that there may be multiple valid answers as long as the difference is minimized.

inputFormat

The first line contains a single integer n indicating the number of elements in the list.

The second line contains n space-separated integers.

outputFormat

Output two lines. The first line should contain the elements of the first sublist separated by spaces, and the second line should contain the elements of the second sublist separated by spaces.

The generated partition must minimize \( |\sum_{a\in S_1}a - \sum_{a\in S_2}a| \).

5
1 2 3 4 5

1 2 4
3 5