004 - 水ようかん (Mizuyokan)

問題

水ようかんとは，おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である．いま，JOI 君の手元には，横長の直方体の形をした水ようかんがひとつある．JOI 君は，今日のおやつとしてこの水ようかんを食べる予定である．

この水ようかんには，縦方向の切れ目が全部で N-1 箇所に入っている．水ようかんの長さは L₁ + L₂ + ... + L_N であり，i 番目 (1 ≦ i ≦ N-1) の切れ目は，左から L₁ + L₂ + ... + L_i の位置にある．

この水ようかんは丸ごと食べるには大きすぎるので，JOI 君は，水ようかんに入っている切れ目から 1 箇所以上を選び，選んだ切れ目に沿って水ようかんを切って，複数のピースに切り分けることにした．ただし，ピースの大きさが不揃いでは見栄えが悪いので，長さ最大のピースと最小のピースの長さの差ができるだけ小さくなるように切ることにした．

長さ最大のピースと最小のピースの長さの差の最小値を求めよ．

制約

• 2 ≦ N ≦ 50
• 1 ≦ L_i ≦ 1000 (1 ≦ i ≦ N)

入力

入力は以下の形式で標準入力から与えられる．

N
L1
L2
:
LN

出力

長さ最大のピースと最小のピースの長さの差の最小値を 1 行で出力せよ．

小課題

小課題 1 [10点]

• N ≦ 15

小課題 2 [27点]

• L_i ≦ 10 (1 ≦ i ≦ N)

小課題 3 [63点]

• 追加の制限はない．

入出力例

入力例 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 つのピースに分割できる．