Minimum Absolute Difference Partition

You are given a list of n integers. Your task is to split this list into exactly two non-empty subsets such that the absolute difference between the sums of the two subsets is minimized.

If there are multiple ways to achieve the minimum difference, you may output the difference from any one valid split.

Note: The two subsets do not have to be contiguous segments of the list. However, each element from the list must belong to one of the two subsets.

The answer should be output as a single integer representing the minimal absolute difference between the sums of the two selected subsets.

We recommend using a brute-force approach with bit masking or combinations if n is small.

inputFormat

The input is given as a single line from standard input (stdin) that contains n + 1 space-separated integers. The first integer denotes the number of elements n in the list. The following n integers represent the elements of the list.

Example:
Input: 5 3 1 4 2 2

outputFormat

Output a single integer to standard output (stdout) which is the minimum absolute difference between the sum of the two subsets.

Example:
Output: 0

## sample

5 3 1 4 2 2

0