Minimal Partition Difference

Given an array of positive integers, partition it into two non-empty subsets so that the absolute difference between the sums of these subsets is minimized. Formally, let (A) be the array and let (S = \sum_{i=1}^{n} A_i). We seek a subset (P) (with at least one element and not the entire array) such that the value (|S - 2\cdot\text{sum}(P)|) is minimized. Your task is to compute and output this minimal difference.

Note: It is guaranteed that the array contains at least two elements.

inputFormat

The input is read from standard input. The first line contains an integer (n) ((n \ge 2)) representing the number of elements in the array. The second line contains (n) space-separated positive integers which represent the array.

outputFormat

Output a single integer which is the minimal absolute difference between the sums of the two subsets, printed to standard output.## sample

4
10 20 15 5

0