Minimum Partition Difference

You are given a list of n integers. Your task is to partition this list into two subsets such that the absolute difference between the sums of the elements in the two subsets is minimized. Formally, if one subset sums to S₁ and the other to S₂, you must minimize \(|S_1 - S_2|\). This problem can be efficiently solved using dynamic programming.

Note: It is not required that the subsets be of equal size, only that the difference in their sums is as small as possible.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains an integer n, the number of integers in the list. The second line contains n space-separated integers representing the list elements.

Example:

5
3 1 4 2 2

outputFormat

Output a single integer to standard output (stdout) representing the minimum possible absolute difference between the sums of the two subsets.

Example:

0

## sample

5
3 1 4 2 2

0

</p>