Minimum Difference Partition

You are given an array of positive integers. Your task is to partition the array into two parts such that the absolute difference between the sum of the elements in the first part and the sum of the elements in the second part is minimized.

Formally, suppose the array is A with n elements and you split it into two subarrays: S1 and S2. Let the sums be:

\( \text{sum}(S_1) \) and \( \text{sum}(S_2) \). The goal is to minimize:

\( |\text{sum}(S_1) - \text{sum}(S_2)| \).

It is guaranteed that all elements are positive integers. Try to achieve an optimal partition based on the given constraints.

inputFormat

The first line contains a single integer n representing the number of elements in the array.

The second line contains n space-separated positive integers representing the array elements.

outputFormat

Output a single integer which is the minimum absolute difference between the sum of the two partitions.

## sample

4
1 3 5 9

0

</p>