Minimum Difference Partition

You are given an array of N non-negative integers. Your task is to partition the array into two subsets such that the absolute difference between the sum of the elements in the two subsets is minimized.

More formally, let the array be \(A = [a_1, a_2, \dots, a_N]\) and let \(S_1\) and \(S_2\) be two partitions of \(A\) (i.e. \(S_1 \cup S_2 = A\) and \(S_1 \cap S_2 = \emptyset\)). You need to minimize the value:

[ \left| \sum_{x \in S_1} x - \sum_{x \in S_2} x \right| ]

It is guaranteed that the input will always be such that a valid partition exists.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (N) denoting the number of elements in the array. The second line contains (N) space-separated integers representing the elements of the array.

outputFormat

Output to standard output (stdout) a single integer which is the minimum absolute difference between the sums of the two partitions.## sample

4
2 4 6 8

0