Minimize Sum Difference

You are given an array of integers \(A = [a_1, a_2, \dots, a_N]\). Your task is to partition this array into two non-empty parts, such that the absolute difference of their sums is minimized. Formally, if one part has sum \(S_1\) and the other has sum \(S_2 = \sum_{i=1}^{N}a_i - S_1\), you need to find the minimum value of \(|S_1 - S_2|\). This can be mathematically represented as:

[ \min_{\substack{S \subset {1,2,\dots, N} \ S \neq \emptyset,\ S \neq {1,2,\dots,N}}}|\sum_{i \in S}a_i - (\sum_{i=1}^{N}a_i - \sum_{i \in S}a_i)| ]

Solve this problem using a dynamic programming approach where you determine all achievable sums up to \(\lfloor \frac{\sum_{i=1}^{N}a_i}{2} \rfloor\) and then choose the one that leads to the minimum difference.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (N) representing 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 to standard output (stdout): the minimum absolute difference between the sums of the two parts.## sample

5
1 2 3 4 5

1