Minimum Partition Difference

You are given an array of N positive integers. Your task is to partition the array into two subsets such that the absolute difference between the sum of the elements in the two subsets is minimized.

Let \( S_1 \) and \( S_2 \) be the sums of the two subsets respectively. The required answer is the minimum value of \( |S_1 - S_2| \).

For example, if the input array is [1, 6, 11, 5], one optimal partition is [1, 5, 6] and [11], resulting in a difference of 1.

inputFormat

The input is read from standard input (stdin) and follows the format below:

• The first line contains a single integer N, which represents the number of elements in the array.
• The second line contains N space-separated integers representing the elements of the array.

outputFormat

Output to standard output (stdout) a single integer which is the minimum absolute difference between the sums of the two subsets.

## sample

4
1 6 11 5

1

</p>