Minimum Subset Sum Difference

You are given a list of n non-negative integers. Your task is to partition the list into two subsets such that the absolute difference between the sum of the subsets is minimized.

Let the list be \(a_1, a_2, \dots, a_n\). Define the total sum as \(S = \sum_{i=1}^{n} a_i\). You need to find a subset with sum \(P\) such that the absolute difference \(|S - 2P|\) is minimized.

For example, given the list [1, 2, 3, 9], the output is 3 because one optimal partition is \(\{1,2,3\}\) and \(\{9\}\), and \(|9 - 6| = 3\).

The solution should read input from stdin and output the answer to stdout.

inputFormat

The first line of input contains a single integer \(n\) representing the number of items.

The second line contains \(n\) space-separated integers representing the values of the items.

outputFormat

Output a single integer which is the minimum possible difference between the sums of two subsets.

## sample

4
1 2 3 9

3

</p>