Minimum Absolute Difference Partition

You are given a set of items, each with a weight. Your task is to partition these items into two groups such that the absolute difference between the total weights of the two groups is minimized. Formally, given a list of weights (w_1,w_2,\dots,w_n) with total sum (T=\sum_{i=1}^{n}w_i), find a subset with sum (S) such that the difference (|T-2S|) is minimized.

For example, if the weights are [1, 2, 3, 4, 5], one optimal partition splits the items into groups with sums 7 and 8, and the minimum possible absolute difference is (1).

inputFormat

Input is given via standard input. The first line contains an integer (n) representing the number of items. The second line contains (n) space-separated integers indicating the weights of the items.

outputFormat

Output a single integer on a new line, representing the minimum possible absolute difference between the sums of the two groups.## sample

5
1 2 3 4 5

1