레이팅 미적용설명
水ようかんとは,おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である.いま,JOI 君の手元には,横長の直方体の形をした水ようかんがひとつある.JOI 君は,今日のおやつとしてこの水ようかんを食べる予定である.
この水ようかんには,縦方向の切れ目が全部で N-1 箇所に入っている.水ようかんの長さは L_1 + L_2 + ... + L_N であり, i 番目 (1 ≦ i ≦ N-1) の切れ目は,左から L_1 + L_2 + ... + L_i の位置にある.
この水ようかんは丸ごと食べるには大きすぎるので,JOI 君は,水ようかんに入っている切れ目から 1 箇所以上を選び,選んだ切れ目に沿って水ようかんを切って,複数のピースに切り分けることにした.ただし,ピースの大きさが不揃いでは見栄えが悪いので,長さ最大のピースと最小のピースの長さの差ができるだけ小さくなるように切ることにした.
長さ最大のピースと最小のピースの長さの差の最小値を求めよ.
제약
2 ≦ N ≦ 50
1 ≦ L_i ≦ 1000 (1 ≦ i ≦ N)
入力・出力
小課題 1 [10点]
N ≦ 15
小課題 2 [27点]
L_i ≦ 10 (1 ≦ i ≦ N)
小課題 3 [63点]
追加の制限はない.
입력 형식
入力は以下の形式で標準入力から与えられる.
N
L_1
L_2
:
L_N
출력 형식
長さ最大のピースと最小のピースの長さの差の最小値を 1 行で出力せよ.
예제 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
문제 정보