JOI 君は妹の JOI 子ちゃんと JOI 美ちゃんと一緒におやつを食べようとしている．今日のおやつは $3$ 人の大好物のバームクーヘンだ．

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

図 1: バームクーヘンの例 $N = 6$，$A_1 = 1$，$A_2 = 5$，$A_3 = 4$，$A_4 = 5$，$A_5 = 2$，$A_6 = 4$

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

課題

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

---

入力

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

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

出力

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

---

制限

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

• $3 \\leqq N \\leqq 100\\,000$．
• $1 \\leqq Ai \\leqq 1\\,000\\,000\\,000$ ($1 \\leqq i \\leqq N$)．

小課題

小課題 1 [5 点]

$N \\leqq 100$ を満たす．

小課題 2 [15 点]

$N \\leqq 400$ を満たす．

小課題 3 [30 点]

$N \\leqq 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