물양갱

문제

물양갱이란 주로 팥으로 만든 소를 틀에 부어 한천으로 굳혀서 만드는 일본 전통 과자이다. 지금 JOI 군의 손에는 가로로 긴 직육면체 모양의 물양갱이 하나 있다. JOI 군은 오늘의 간식으로 이 물양갱을 먹을 예정이다.

이 물양갱에는 세로 방향의 칼집이 전부 $N-1$ 군데 들어가 있다. 물양갱의 길이는 $L_1\,+\,L_2\,+\,...\,+\,L_N$ 이고, $i$ 번째 $(1\,\,\le\,\,i\,\,\le\,\,N-1)$ 칼집은 왼쪽에서 $L_1\,+\,\,L_2\,+\,\,...\,+\,\,L_i$ 의 위치에 있다.

이 물양갱은 통째로 먹기에는 너무 크기 때문에, JOI 군은 물양갱에 들어가 있는 칼집 중 $1$ 군데 이상을 골라, 고른 칼집을 따라 물양갱을 잘라서 여러 개의 조각으로 나누기로 했다. 단, 조각의 크기가 들쭉날쭉하면 보기에 좋지 않으므로, 길이가 가장 긴 조각과 가장 짧은 조각의 길이 차이가 가능한 한 작아지도록 자르기로 했다.

길이가 가장 긴 조각과 가장 짧은 조각의 길이 차이의 최솟값을 구하시오.

제한

• $2\,\,\le\,\,N\,\,\le\,\,50$
• $1\,\,\le\,\,L_i\,\,\le\,\,1000\,(1\,\,\le\,\,i\,\,\le\,\,N)$

서브태스크

서브태스크 1 [10점]

• $N\,\,\le\,\,15$

서브태스크 2 [27점]

• $L_i\,\,\le\,\,10\,(1\,\,\le\,\,i\,\,\le\,\,N)$

서브태스크 3 [63점]

• 추가 제약이 없다.

입력과 출력

입력
입력은 다음 형식으로 표준 입력에서 주어진다.
$N$
$L_1$
$L_2$
:
$L_N$

출력
길이가 가장 긴 조각과 가장 짧은 조각의 길이 차이의 최솟값을 $1$ 줄로 출력한다.

예제 입력 1

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

예제 출력 1

2

이 예제에서는 $4$ 번째 및 $7$ 번째 칼집을 따라 잘라서, 길이가 $17,\,19,\,18$ 인 $3$ 개의 조각으로 나눌 수 있다. 이때 가장 긴 조각은 길이가 $19$ 이고 가장 짧은 조각은 길이가 $17$ 이므로, 길이 차이는 $2$ 가 된다. 이것이 최솟값이므로 $2$ 를 출력한다.

예제 입력 2

2
1
10

예제 출력 2

9

크기가 아무리 들쭉날쭉하더라도 반드시 $1$ 군데 이상을 잘라야 한다.

예제 입력 3

5
5
5
5
5
5

예제 출력 3

0

이 예제에서는 물양갱을 정확히 같은 크기의 $5$ 개의 조각으로 나눌 수 있다.