Minimum Absolute Difference Partition

Given a list of integers, consider the absolute values of each element. Your task is to partition these absolute values into two subsets such that the absolute difference between the sum of the elements in the two subsets is minimized.

Formally, let \(A = [a_1, a_2, \dots, a_n]\) be the given list. Define \(b_i = |a_i|\) for each \(i\). You need to split \(B = [b_1, b_2, \dots, b_n]\) into two subsets \(S_1\) and \(S_2\) such that the value \[ \left| \sum_{x \in S_1} x - \sum_{x \in S_2} x \right| \] is minimized. Output this minimum possible absolute difference.

You are required to implement a solution that reads from standard input and writes to standard output.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the list. The second line contains \(n\) space-separated integers, which may be positive, negative, or zero.

outputFormat

Output a single integer representing the minimum absolute difference between the sums of the two subsets formed from the absolute values of the given numbers.

## sample

4
1 -2 3 4

0

</p>