페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8365
서브태스크

팥양갱 2s 1024MB

문제

팥양갱이란, 주로 팥으로 만든 앙금을 틀에 부어 한천으로 굳혀서 만드는 과자이다. 지금, 정올이의 손에는 가로로 긴 직육면체 모양의 팥양갱이 하나 있다. 정올이는 오늘 간식으로 이 팥양갱을 먹을 예정이다.

이 팥양갱에는 세로 방향의 절취선이 총 N-1곳 들어 있다. 팥양갱의 길이는 L₁ + L₂ + ... + L_N이며, 각 i (1 ≦ i ≦ N-1)에 대해, i번째 절취선은 왼쪽에서 L₁ + L₂ + ... + L_i의 위치에 있다.

이 팥양갱은 통째로 먹기에는 너무 크므로, 정올이는 팥양갱에 있는 절취선 중 1곳 이상을 선택하여, 선택한 절취선을 따라 팥양갱을 잘라 여러 개의 조각으로 나누기로 하였다. 단, 조각의 크기가 고르지 않으면 보기 흉하므로, 길이가 가장 긴 조각과 가장 짧은 조각의 길이 차이가 가능한 한 작아지도록 자르기로 하였다.

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


입력

입력은 다음 형식으로 표준 입력을 통해 주어진다.

N

L₁

L₂

:

L_N

제한
2 ≦ N ≦ 50
1 ≦ L_i ≦ 1000 (1 ≦ i ≦ N)


출력

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


부분문제

번호 점수 조건
#110점

N ≦ 15

#227점

L_i ≦ 10 (1 ≦ i ≦ N)

#363점

추가 제약 조건 없음


예제 #1

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

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


예제 #2

2
1
10
9

아무리 크기가 고르지 않더라도, 반드시 한 곳 이상을 잘라야 한다.


예제 #3

5
5
5
5
5
5
0

이 예제에서는 팥양갱을 딱 같은 크기의 5개 조각으로 분할할 수 있다.



출처

JOI 2018 예선
로그인해야 코드를 작성할 수 있어요.