Problem Description

Your dinner tonight is pizza. There are $N$ pieces numbered from $1$ to $N$ arranged in clockwise order. Note that piece $N$ is adjacent to piece $1$.

The deliciousness of piece $i$ is $a_i$.

You will choose some consecutive pieces to eat. For example, when there are $10$ pieces of pizza, you can choose pieces $8, 9, 10, 1, 2$ to eat, but you cannot choose pieces $1, 3, 5$ to eat.

Let $X$ be the sum of the deliciousness of the pieces you eat, and $Y$ be the sum of the deliciousness of the remaining pieces. Find the minimum possible value of $|X - Y|$.

Input Format

The input is given from the standard input in the following format:

$N$ $a_1$ $\cdots$ $a_N$

Output Format

Output the minimum possible value of $|X - Y|$.

Sample Input and Output

Sample Input #1

4
10 20 40 30

Sample Output #1

20

Sample Input #2

20
13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9

Sample Output #2

1

Notes/Hints

Constraints

• All given inputs are integers.
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i \leq 10^9$

Sample Explanation 1

• Choosing pieces $4, 1, 2$ to eat is one of the optimal choices.
• In this case, the sum of the deliciousness of the pieces eaten $X$ is $30 + 10 + 20 = 60$, and the sum of the deliciousness of the remaining pieces $Y$ is $40$, so $|X - Y|$ is $20$.
• Note that choosing pieces $1, 3$ or pieces $2, 4$ does not satisfy the condition of choosing consecutive pieces.

见题面 Input 部分

见题面 Output 部分