#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/c

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/c

Repovive

Circular Split - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

7C. Circular Split

1500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 1sMemory: 256 MB

There are $n$ numbers written around a circle. You want to divide the circle into two non-empty contiguous parts, so that the absolute difference between the sums of the two parts is as small as possible.

More formally, you are given an array $a_1, a_2, \ldots, a_n$ . The array is circular, so $a_n$ is adjacent to $a_1$ . A contiguous part on the circle is a non-empty sequence of consecutive elements while moving around the circle. For example, $a_{n-1}, a_n, a_1, a_2$ form one contiguous part.

Choose two different gaps between adjacent elements and cut the circle at those gaps. This creates two contiguous parts. Both parts must be non-empty.

Find the minimum possible absolute difference between the sums of the two parts.

Constraints

$2 \le n \le 2 \times 10^5$
$1 \le a_i \le 1000$

Input

n

a_1 \quad a_2 \quad \cdots \quad a_n

Output

ans

Samples

Input

2
3 10

Explanation

The only possible division puts index $1$ in one part and index $2$ in the other part. Their sums are $3$ and $10$ , so the answer is $|3-10|=7$ .

Output

Input

4
1 2 3 4

Explanation

Cut the circle so that indices $2,3$ are in one part and indices $4,1$ are in the other part. The two sums are $2+3=5$ and $4+1=5$ , so the answer is $|5-5|=0$ .

Output

Input

5
2 7 4 1 6

Explanation

Cut the circle so that indices $1,2$ are in one part and indices $3,4,5$ are in the other part. The two sums are $2+7=9$ and $4+1+6=11$ , so the difference is $|9-11|=2$ . It is impossible to make the difference smaller.

Output

Choose two different gaps between adjacent elements and cut the circle at those gaps. This creates two contiguous parts. Both parts must be non-empty.

Find the minimum possible absolute difference between the sums of the two parts.

$2 \le n \le 2 \times 10^5$
$1 \le a_i \le 1000$

n

a_1 \quad a_2 \quad \cdots \quad a_n

ans

The only possible division puts index $1$ in one part and index $2$ in the other part. Their sums are $3$ and $10$ , so the answer is $|3-10|=7$ .

Cut the circle so that indices $2,3$ are in one part and indices $4,1$ are in the other part. The two sums are $2+3=5$ and $4+1=5$ , so the answer is $|5-5|=0$ .