Minimum Absolute Difference Partition

You are given a list of N positive integers. Your task is to partition the set of integers into two non-empty subsets \(S_1\) and \(S_2\) such that the absolute difference between the sums of the subsets is minimized. In other words, if the sum of the integers in subset \(S_1\) is \(s_1\) and the sum in \(S_2\) is \(s_2\), you need to minimize \(|s_1 - s_2|\).

Note: Both subsets must be non-empty.

Example:

Input:
6
3 1 4 2 2 1
Output:
1

</p>

The optimal partition gives an absolute difference of 1.

inputFormat

The input is read from standard input and contains two lines:

• The first line contains an integer \(N\) (\(N \geq 2\)), representing the number of elements in the list.
• The second line contains \(N\) positive integers separated by spaces.

For example:

6
3 1 4 2 2 1

outputFormat

Output a single integer denoting the minimum possible absolute difference between the sums of the two subsets. The answer should be printed to standard output.

For example:

1

## sample

6
3 1 4 2 2 1

1