#215874. [JOI 2014 Final] バームクーヘン

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

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

:::align{center}

図 1: バームクーヘンの例 , , , , , , :::

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

課題

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

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

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

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

样例输入 1

6
1
5
4
5
2
4

样例输出 1

6

样例输入 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

入出力例

:::align{center}

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

制限

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

• ()

小課題

小課題 1 [5 点]

を満たす。

小課題 2 [15 点]

を満たす。

小課題 3 [30 点]

を満たす。

小課題 4 [50 点]

追加の制限はない。