Minimum Subarray Sum Difference

You are given an array of n non-negative integers. Your task is to split the array into two subarrays such that the absolute difference of their sums is minimized.

Let \(T\) denote the total sum of the array, and \(S\) be the sum of one of the subarrays. The difference between the two subarrays is expressed as \( |T - 2S| \). Your goal is to choose \(S\) as close as possible to \(T/2\) in order to minimize the expression above.

This problem can be solved using dynamic programming. You need to determine which subset sums are possible and then find the subset with the largest sum not exceeding \(T/2\), which will yield the minimum difference.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n representing the number of elements in the array.
• The second line contains n space-separated integers, denoting the array elements.

outputFormat

Output a single integer to standard output (stdout) denoting the minimum difference between the sums of two subarrays.

## sample

4
1 2 3 9

3

</p>