Minimum Weight Difference Partition

You are given a set of items, each with a given weight. Your task is to divide the items into two groups such that the difference between the total weights of the two groups is minimized.

Let \(T\) be the sum of all item weights and let \(S\) be the total weight of one of the groups. The goal is to minimize the difference \(T - 2S\). In other words, you need to choose \(S\) as close as possible to \(\frac{T}{2}\). If there is only one item, then the answer is simply the weight of that item.

inputFormat

The input consists of multiple test cases. For each test case, the first line contains an integer (N) representing the number of items. The second line contains (N) space-separated integers denoting the weights of the items. The input ends with a test case where (N = 0), which should not be processed.

outputFormat

For each test case, output a single line containing the minimum possible difference between the total weights of the two groups.## sample

4
1 6 11 5
0

1