Minimum Partition Difference

You are given a set of n items, each having a weight. Your task is to partition the set into two groups such that the absolute difference between the sum of weights in the two groups is minimized.

Let \( S_1 \) and \( S_2 \) be the sums of the weights in the two groups respectively. You need to minimize:

[ |S_1 - S_2| ]

Input Constraints:

• 1 \(\leq n \leq 10^5\)
• Each weight is a positive integer.

The problem requires you to read from standard input and output the result to standard output.

inputFormat

The input is given via standard input. The first line contains an integer n, denoting the number of items. The second line contains n space separated integers representing the weights of the items.

outputFormat

Output the minimum possible absolute difference between the sum of the weights of the two groups to standard output.

## sample

5
1 2 3 4 5

1

</p>