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

問題

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

図1: バームクーヘンの例 N = 6, A₁ = 1, A₂ = 5, A₃ = 4, A₄ = 5, A₅ = 2, A₆ = 4

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

課題

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

入力

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

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

出力

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

制限

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

• 3 ≤ N ≤ 100000．
• 1 ≤ A_i ≤ 1000000000 (1 ≤ i ≤ N)．

小課題

小課題 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