Problem Description

Mizuyokan is a traditional Japanese confectionery made by pouring a bean paste mixture into a mold and solidifying it with agar. Now, JOI has a Mizuyokan in the shape of a long rectangular prism. JOI plans to eat this Mizuyokan as a snack.

This Mizuyokan has a total of $N-1$ vertical cuts. The total length of the Mizuyokan is $L_1 + L_2 + ... + L_N$, and the $i$-th cut ($1 ≦ i ≦ N-1$) is located at the position $L_1 + L_2 + ... + L_i$ from the left.

Since the Mizuyokan is too large to eat whole, JOI decided to cut it along one or more of these cuts to divide it into multiple pieces. However, the pieces should look neat, so the difference between the length of the longest piece and the shortest piece should be as small as possible.

Find the minimum difference between the length of the longest piece and the shortest piece.

Input Format

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

$N$ $L_1$ $L_2$ : $L_N$

Output Format

Output the minimum difference between the length of the longest piece and the shortest piece in one line.

Sample Input and Output

Sample Input #1

11
2
3
8
4
7
6
6
5
1
7
5

Sample Output #1

2

Sample Input #2

2
1
10

Sample Output #2

9

Sample Input #3

5
5
5
5
5
5

Sample Output #3

0

Notes/Hints

Constraints

• $2 ≦ N ≦ 50$
• $1 ≦ L_i ≦ 1000$ ($1 ≦ i ≦ N$)

Subtask 1 [10 points]

• $N ≦ 15$

Subtask 2 [27 points]

• $L_i ≦ 10$ ($1 ≦ i ≦ N$)

Subtask 3 [63 points]

• No additional constraints.

Sample Explanation 1

In this example, by cutting along the 4th and 7th cuts, the Mizuyokan can be divided into 3 pieces of lengths 17, 19, and 18. The longest piece is 19, and the shortest piece is 17, so the difference in length is 2. This is the minimum value, so output 2.

Sample Explanation 2

No matter how uneven the sizes are, at least one cut must be made.

Sample Explanation 3

In this example, the Mizuyokan can be divided into 5 pieces of exactly the same size.

见题面 Input 部分

见题面 Output 部分