Mizuyokan

Interview

Time limit2sMemory limit512 MB

Summary

Given a bar divided by N-1 score lines into segments of given lengths, cut along some lines so the longest and shortest resulting pieces differ as little as possible.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Prefix sum, Greedy
Solved: No attempts yet

Problem

Mizuyokan is a Japanese sweet made by pouring a paste of red beans into a mould and setting it with agar. JOI has one bar of mizuyokan shaped like a long rectangular block. He plans to eat it as today's snack.

The bar carries $N-1$ score lines that run across it. The whole bar has length $L_1 + L_2 + \dots + L_N$ , and the $i$ -th score line $(1 \le i \le N-1)$ sits at distance $L_1 + L_2 + \dots + L_i$ from the left end.

The bar is too large to eat whole, so JOI picks at least one of the score lines and cuts the bar along every picked line, splitting it into several pieces. Pieces of uneven size look bad, so he wants the difference between the longest piece and the shortest piece to be as small as possible.

Find the smallest possible difference between the length of the longest piece and the length of the shortest piece.

Input

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

N
L_1
L_2
...
L_N

The first line has the number of blocks $N$ . Each of the next $N$ lines has $L_i$ on the $i$ -th of them.

Output

Print the smallest possible difference between the longest piece and the shortest piece on one line.

Constraints

$2 \le N \le 50$
$1 \le L_i \le 1000 \ (1 \le i \le N)$
Every input value is an integer.

Examples3

Example 1
Input
```
11
2
3
8
4
7
6
6
5
1
7
5
```
Expected output
```
2
```
Example 2
Input
```
2
1
10
```
Expected output
```
9
```
Example 3
Input
```
5
5
5
5
5
5
```
Expected output
```
0
```