Minimize Absolute Difference

You are given an array of n integers. Your task is to split the array into two non-empty contiguous subarrays such that the absolute difference between the sum of the first subarray and the sum of the second subarray is minimized.

Formally, if the array is A and you split it at a position i (where 1 \le i < n), then you have two subarrays:

• The left subarray: \(A_1, A_2, \dots, A_i\)
• The right subarray: \(A_{i+1}, A_{i+2}, \dots, A_n\)

You need to find the minimum value of \(|S_{left} - S_{right}|\) over all valid i, where \(S_{left}\) and \(S_{right}\) are the sums of the left and right subarrays respectively.

Input/Output details:

Read the input from stdin and output the result to stdout.

inputFormat

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

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

outputFormat

Output a single integer which is the minimum absolute difference between the sums of two contiguous subarrays obtained by splitting the array.

## sample

5
1 3 3 2 4

1