347. Minimize Sum Difference by Partitioning into Two Equal Halves

0

Hard

Given an array of integers with an even size, you need to divide the array into two equal halves in such a way that the absolute difference between the sums of the two halves is minimized.

In other words, if the sums of the two halves after partitioning are Sum1 and Sum2 respectively, you need to find the minimum value of abs(Sum1 - Sum2).

In other words, if the sums of the two halves after partitioning are Sum1 and Sum2 respectively, you need to find the minimum value of abs(Sum1 - Sum2).

Input Format

The first line contains an even integer n, representing the size of the array. The second line contains n space-separated integers, which are the elements of the array.

Output Format

Print the minimum possible absolute difference.

Example

Input

4
3 7 9 3

Output

2

Constraints

1<=n<=30

Elements of the array are within the range of -10^6 to 10^6

Elements of the array are within the range of -10^6 to 10^6

Loading...

View Submissions

Console