Minimizing Partition Difference

Given an array of integers, partition the array into two subsets such that the absolute difference between the sums of the two subsets is minimized.

You need to output the minimized absolute difference. This problem can be efficiently solved using dynamic programming, where you determine the possible subset sums up to \(\lfloor \frac{S}{2} \rfloor\) (with \(S\) being the total sum) and then find the closest achievable sum.

Note: The input is provided via stdin and the output should be printed to stdout.

inputFormat

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 a single integer representing the minimum absolute difference between the sums of the two subsets.

## sample

4
1 6 11 5

1

</p>