Minimal Server Capacity Difference

You are given n servers with their capacities. Your task is to partition the servers into two groups such that the absolute difference between the total capacities of the two groups is minimized.

Formally, let \( S_1 \) and \( S_2 \) be the sums of the capacities of the servers in the two groups. You need to minimize \( |S_1 - S_2| \). It is allowed for one group to be empty.

Example:

Input: n = 3, capacities = [8, 5, 6]
Output: 3
Explanation: One optimal partition is: Group 1: [8, 5] (sum = 13) and Group 2: [6] (sum = 6), and |13 - 6| = 7. However, a better partition is: Group 1: [8, 6] (sum = 14) and Group 2: [5] (sum = 5), yielding |14 - 5| = 9. 
Actually, the correct optimal partition is: Group 1: [8] (sum = 8) and Group 2: [5,6] (sum = 11), thus |8 - 11| = 3.

Note that the input size is small enough to allow exponential-time methods.

inputFormat

The input is read from standard input and has the following format:

• The first line contains a single integer \( n \) (the number of servers).
• The second line contains \( n \) space-separated integers, where each integer represents the capacity of a server.

outputFormat

Output a single integer which is the minimum possible absolute difference between the total capacities of the two groups.

## sample

3
8 5 6

3

</p>