Minimum Difference Partition

You are given (N) barns, each containing a certain number of cows. You are allowed to swap barns arbitrarily. After arranging the barns in any order, split them into two groups. Your task is to partition the cows into two groups such that the absolute difference between the sum of cows in the two groups is minimized. Formally, let the total number of cows be (S = \sum_{i=1}^{N} a_i) and let one group have a total of (s) cows. You need to minimize (|S - 2s|). Note that the two groups can have different sizes.

inputFormat

The first line contains a single integer (N) (the number of barns). The second line contains (N) space-separated integers, where each integer represents the number of cows in a barn.

outputFormat

Output a single integer representing the minimum possible absolute difference between the sum of cows in the two groups.## sample

6
1 2 3 4 5 6

1