Problem Statement

There is one stick. This stick has $N-1$ notches, which divide it into $N$ parts.

The lengths of the parts are $L_1,L_2,\dots,L_N$ in order from one end.

When choosing one notch and breaking the stick there to obtain two sticks, find the minimum possible absolute value of the difference between the lengths of the two resulting sticks.

Here, the width of a notch can be ignored, and the length of each resulting stick is the sum of the lengths of the parts it contains.

Constraints

• $2 \leq N \leq 100$
• $1 \leq L_i \leq 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$
• $L_1$ $L_2$ $\dots$ $L_N$

Output

Output the answer.

4
5 2 3 8

2

Breaking the stick at each notch results in the following:

• Breaking at the first notch from the end results in two sticks of lengths $5$ and $13$, with an absolute difference of $8$.
• Breaking at the second notch from the end results in two sticks of lengths $7$ and $11$, with an absolute difference of $4$.
• Breaking at the third notch from the end results in two sticks of lengths $10$ and $8$, with an absolute difference of $2$.

7
31 41 59 26 53 58 97

51

10
67011 35764 33042 24098 63738 98760 17199 68579 21812 45408

28105

• Source: AtCoder ABC 472 B