Minimum Absolute Difference Partition

You are given an array of n integers. Your task is to partition the array into two subsets such that the absolute difference between the sums of the two subsets is minimized.

Formally, let \(S\) be the sum of all elements and \(s\) be the sum of one of the subsets. You need to choose a subset such that the value of \(\left|S - 2s\right|\) is minimized. In other words, if \(s^*\) is the maximum achievable sum not exceeding \(\lfloor S/2 \rfloor\), then the answer is:

\[ \text{Answer} = S - 2 \times s^* \]

This is a classic dynamic programming problem that is analogous to the Subset Sum Problem and the Partition Problem.

inputFormat

The first line of input contains an integer n, 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 possible absolute difference between the sums of the two subsets.## sample

1
7

7