Array Partition :
Difficulty Level : Hard
Submissions : 177
Asked In :
Marks :10
: 2 | : 1
Given an array $$$X$$$, partition it into two subsets $$$A$$$ and $$$B$$$, such that the following conditions hold :
- Each element of $$$X$$$ should belong to either $$$A$$$ or $$$B$$$, i.e $$$A$$$ intersection $$$B$$$ = empty set and $$$A$$$ union $$$B$$$ = $$$X$$$
- Sum of values in set $$$A$$$ should be strictly greater than sum of values in set $$$B$$$
- Number of elements in set $$$A$$$ should be minimal
Please note that $$$A$$$ and $$$B$$$ can have multiple occurrences of the same integer.
Out of all such possibilities of $$$A$$$, output the one which has the least sum, and print the one which is lexicographically maximum out of them in sorted order.
Input
First line contains N - the number of elements in $$$X$$$ (1 <= N <= 1000)
Second line contains N space separated integers, $$$X_{i}$$$ (1 <= $$$X_{i}$$$ <= 1000)
Sum of all $$$X_{i}$$$ <=1000.
Output
Output the elements belonging in set $$$A$$$, in sorted order
Examples
Input
5 3 7 5 6 2
Output
5 7
Input
20 2 3 4 4 5 9 7 8 6 10 4 5 10 10 8 4 6 4 10 1
Output
6 6 9 10 10 10 10
