Minimize Subset Sum Difference

You are given a set of n positive integers. Your task is to partition the set into two subsets A and B such that the absolute difference between the sums of the elements in the two subsets is minimized. In mathematical terms, if:

$$S_A = \sum_{a \in A} a, \quad S_B = \sum_{b \in B} b, $$

then you need to minimize

$$|S_A - S_B|.$$

For example, if the set is [3, 1, 4, 2, 2], one optimal partition is A = [3, 2, 2] and B = [1, 4] with both subsets summing to 7, hence the minimum difference is 0.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains an integer n representing the number of elements in the array.
• The second line contains n space-separated integers, the elements of the array.

outputFormat

Output a single integer to standard output (stdout) - the minimum possible absolute difference between the sums of the two subsets.

## sample

5
3 1 4 2 2

0