Mizuyokan

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.

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.

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

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