물양갱

면접 대비

시간 제한2초메모리 제한512 MB

요약

길이가 주어진 구간들로 나뉜 막대에서 일부 경계만 잘라 만들어진 조각들 중 가장 긴 것과 가장 짧은 것의 길이 차이를 최소로 만든다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색, 누적 합, 그리디
정답자: 아직 제출이 없습니다

문제

물양갱은 주로 팥으로 만든 앙금을 틀에 부은 뒤 한천으로 굳혀 만드는 일본 과자다. 지금 JOI 군의 손에는 가로로 긴 직육면체 모양의 물양갱이 하나 있다. JOI 군은 오늘 간식으로 이 물양갱을 먹을 생각이다.

이 물양갱에는 세로 방향 칼집이 모두 $N-1$ 개 들어가 있다. 물양갱 전체의 길이는 $L_1 + L_2 + \dots + L_N$ 이고, $i$ 번째 $(1 \le i \le N-1)$ 칼집은 왼쪽 끝에서 $L_1 + L_2 + \dots + L_i$ 만큼 떨어진 곳에 있다.

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

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

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

N
L_1
L_2
...
L_N

첫 줄에 블록의 개수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄 중 $i$ 번째 줄에 $L_i$ 가 주어진다.

출력

가장 긴 조각과 가장 짧은 조각의 길이 차이의 최솟값을 한 줄에 출력하라.

제한

$2 \le N \le 50$
$1 \le L_i \le 1000 \ (1 \le i \le N)$
모든 입력 값은 정수다.

예제3

예제 1
입력
```
11
2
3
8
4
7
6
6
5
1
7
5
```
예상 출력
```
2
```
예제 2
입력
```
2
1
10
```
예상 출력
```
9
```
예제 3
입력
```
5
5
5
5
5
5
```
예상 출력
```
0
```