Minimum Coin Value Difference Partition

Given n coins with possibly different values, where the value of the i-th coin is \(v_i\), you are to partition the coins into two groups such that the difference in the number of coins between the two groups is at most 1. In other words, if \(n\) is even then each group must contain exactly \(\frac{n}{2}\) coins; if \(n\) is odd, one group will contain \(\lfloor\frac{n}{2}\rfloor\) coins and the other \(\lfloor\frac{n}{2}\rfloor+1\) coins. The goal is to minimize the absolute difference of the total values of the coins in the two groups.

The value difference is defined as \(|T - 2S|\), where \(T\) is the sum of all coins and \(S\) is the sum of coins in one of the groups.

inputFormat

The first line contains a positive integer \(n\) which is the number of coins. The second line contains \(n\) space-separated integers \(v_1, v_2, \ldots, v_n\), where \(v_i\) denotes the value of the i-th coin.

outputFormat

Output a single integer representing the minimum possible absolute difference between the total values of the two groups.

sample

4
1 2 3 4

0