Cutting the Tape

Interview

Time limit1sMemory limit128 MB

Summary

Split the row of integers into two nonempty parts so the absolute difference of the two part sums is as small as possible.

Level: Easy3 of 10
Topics: Prefix sum, Array
Solved: No attempts yet

Problem

Someone found a long tape at home and wrote a row of integers on it. Now they want to cut the tape at a single point, splitting it into two pieces, so that the difference between the sum of the numbers on one piece and the sum on the other piece is as close to $0$ as possible. Each piece must contain at least one number. Find the minimum possible absolute value of that difference.

Input

The first line contains the count of numbers on the tape, $n$ ( $2 \le n \le 10^6$ ). The second line contains the $n$ integers $a_i$ ( $-10^3 \le a_i \le 10^3$ ) written on the tape, in order.

Output

Print, on a single line, the minimum absolute value of the difference between the sums of the two pieces.

Hint

For example, if the sequence is $1, 2, 3, 4, 5, 6$ , cutting after the fourth number splits it into $1, 2, 3, 4$ and $5, 6$ , and the absolute value of the difference of the two sums is $|(1 + 2 + 3 + 4) - (5 + 6)| = 1$ .

Examples2

Example 1
Input
```
6
1 2 3 4 5 6
```
Expected output
```
1
```
Example 2
Input
```
2
5 5
```
Expected output
```
0
```