005 - バームクーヘン (Baumkuchen)

時間制限 2 秒 / メモリ制限 256 MB / 得点 100 / x 1 /


TLE
2sec
MLE
256MB
得点
100

問題

 JOI 君は妹の JOI 子ちゃんと JOI 美ちゃんと一緒におやつを食べようとしている.今日のおやつは 3 人の大好物のバームクーヘンだ.
 バームクーヘンは下図のような円筒形のお菓子である.3 人に分けるために,JOI 君は半径方向に刃を 3 回入れて,これを 3 つのピースに切り分けなければならない.ただしこのバームクーヘンは本物の木材のように固いので,刃を入れるのは簡単ではない.そのためこのバームクーヘンにはあらかじめ N 個の切れ込みが入っており,JOI 君は切れ込みのある位置でのみ切ることができる.切れ込みに 1 から N まで時計回りに番号をふったとき,1 ≤ iN - 1 に対し, i 番目の切れ込みと i + 1 番目の切れ込みの間の部分の大きさは Ai である.また N 番目の切れ込みと 1 番目の切れ込みの間の部分の大きさは AN である.



図1: バームクーヘンの例 N = 6, A1 = 1, A2 = 5, A3 = 4, A4 = 5, A5 = 2, A6 = 4

 妹思いの JOI 君は,バームクーヘンを 3 つのピースに切り分けたあと,自分は最も小さいピースを選び,残りの 2 つのピースを 2 人の妹にあげることにした.一方で,JOI 君はバームクーヘンが大好物なので,できるだけたくさん食べたいと思っている.最も小さいピースの大きさが最大になるように切ったとき,JOI 君が食べることになるピースの大きさはいくらになるだろうか.

課題

 切れ込みの個数 N と,各部分の大きさを表す整数 A1,...,AN が与えられる.バームクーヘンを3 つに切り分けたときの,最も小さいピースの大きさの最大値を出力するプログラムを作成せよ.

入力

 標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N が書かれている.これはバームクーヘンに N 個の切れ込みがあることを表す.
  • 続くN 行のうちの i 行目(1 ≤ iN) には,整数 Ai が書かれている.これは i 番目の切れ込みと i + 1 番目の切れ込みの間の部分 (i = N のときは N 番目の切れ込みと 1 番目の切れ込みの間の部分) の大きさが Ai であることを表す.

出力

 標準出力に,バームクーヘンを3 つに切り分けたときの,最も小さいピースの大きさの最大値を表す整数を1 行で出力せよ.

制限

 すべての入力データは以下の条件を満たす.

  • 3 ≤ N ≤ 100000.
  • 1 ≤ Ai ≤ 1000000000 (1 ≤ iN).

小課題

小課題 1 [5点]

 N ≤ 100 を満たす.

小課題 2 [15 点]

 N ≤ 400 を満たす.

小課題 3 [30 点]

 N ≤ 8 000 を満たす.

小課題 4 [50 点]

 追加の制限はない.

入出力例

入力例 1

6
1
5
4
5
2
4

出力例 1

6

図2: 1 番目の切れ込みと 3 番目の切れ込みと 5 番目の切れ込みで切るのが最善である.

入力例 2

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

出力例 2

213