740. 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 a way that minimizes the absolute difference between the sums of the two halves.

In other words, let's denote the sums of the two halves after partitioning as Sum1 and Sum2 respectively. Your task is to find the minimum value of abs(Sum1 - Sum2).

In other words, let's denote the sums of the two halves after partitioning as Sum1 and Sum2 respectively. Your task is to find the minimum value of abs(Sum1 - Sum2).

Input Format

The first line contains a single even integer n. The second line contains n space-separated integers representing 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