Minimum Absolute Difference Partition

You are given an array of integers. Partition 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.

Let (S_{left}) be the sum of the first part and (S_{total} - S_{left}) be the sum of the second part. Find the minimum value of (|S_{left} - (S_{total} - S_{left})|).

Note: The array must be split into two contiguous parts, and both parts must be non-empty.

inputFormat

The input is read from standard input (stdin).

The first line contains a single integer N (where N (\ge 2)) which is the number of elements in the array.

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

outputFormat

Output a single integer to standard output (stdout), which is the minimum absolute difference between the sums of the two parts after partitioning.## sample

6
3 1 2 4 3 6

1