Minimal Coin Partition Difference

Sasha has a collection of coins, each with a specific value. She wants to split these coins into two groups such that the absolute difference between the sums of the coins in the two groups is minimized.

You are given an integer \(n\) representing the number of coins, followed by \(n\) space-separated integers which represent the values of the coins. Your task is to compute the minimum possible difference between the sum of coins in the two groups.

Mathematically, if the sums of the two groups are \(S_1\) and \(S_2\), you need to find \( |S_1 - S_2| \) minimized over all possible partitions.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) which is the number of coins.
• The second line contains \(n\) space separated integers, the values of the coins.

outputFormat

Output a single integer: the minimal possible difference between the two groups of coins.

## sample

5
1 2 3 4 5

1

</p>