Minimizing Weight Difference Between Two Bags

You are given a list of positive integers representing weights. Your task is to divide these weights into two groups (bags) such that the absolute difference between the sums of the weights in the two groups is minimized.

For example, if the weights are [5, 3, 8, 6], one optimal partition is {5, 8} and {3, 6} resulting in sums 13 and 9 respectively, and the minimum difference is |13 - 9| = 4. (Note: there might be a different partition leading to 0 difference, which is even better.)

Note: You need to compute and output the minimal possible difference. The problem is equivalent to finding a subset of weights that is as close as possible to half of the total sum. All input weights are guaranteed to be positive integers.

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains a single integer n denoting the number of weights.
2. The second line contains n space-separated integers representing the weights.

outputFormat

Output a single integer to stdout representing the minimum possible absolute difference between the sums of two groups when the weights are optimally partitioned.

## sample

4
5 3 8 6

0

</p>