Minimum Difference Partition

You are given a set of n items, each with a positive integer weight. Your task is to divide these items into two groups such that the absolute difference between the sum of the weights in the two groups is minimized. In other words, if one group has total weight s₁ and the other has total weight s₂, you need to minimize $$|s_1 - s_2|$$.

Example:

Input:
5
3 1 4 2 2
Output:
0

</p>

Here, one possible partition is {3,1,2} and {4,2}, both having a total weight of 6.

inputFormat

The input is given from stdin in the following format:

• The first line contains an integer n representing the number of items.
• The second line contains n space-separated integers, where each integer represents the weight of an item.

outputFormat

Output a single integer to stdout – the minimum possible absolute difference between the sums of the weights of the two groups.

## sample

5
3 1 4 2 2

0

</p>