물양갱

물양갱은 주로 팥으로 만든 앙금을 틀에 부은 뒤 한천으로 굳혀 만드는 일본 과자다. 지금 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)$
• 모든 입력 값은 정수다.