Minimum Sweetness Difference Partition

Serval has just received a collection of n candies, each with a certain sweetness level. His task is to divide these candies into two non-empty subsets such that the absolute difference between the total sweetness of the two subsets is minimized.

Let \( S_1 \) and \( S_2 \) represent the sums of the sweetness levels in each subset respectively. The objective is to minimize \( |S_1 - S_2| \). It is guaranteed that n ≥ 2 so that both subsets are non-empty.

This problem can be approached using a dynamic programming technique similar to the Knapsack problem. The idea is to find a subset with a sum as close as possible to half of the total sum of all candies.

inputFormat

The input is given from stdin and consists of two lines:

• The first line contains an integer \( n \) (number of candies).
• The second line contains \( n \) space-separated integers representing the sweetness levels of the candies.

outputFormat

Output a single integer to stdout representing the minimum absolute difference between the sums of the two subsets.

## sample

3
8 4 5

1

</p>