バームクーヘン (Baumkuchen)

给定一个被切成 $n$ 段的圆环，第 $i$ 个切口到第 $i+1$ 个切口的距离为 $A_i$，特别地，切口 $n$ 到 $1$ 的距离为 $A_n$。 现在要将这个圆环从三个切口处分成三段，使得最短的一段长度尽可能的长。求出这个最大长度。 - 对于 $5\%$ 的数据，$n\le 100$； - 对于 $20\%$ 的数据，$n\le 400$； - 对于 $50\%$ 的数据，$n\le 8000$； - 对于 $100\%$ 的数据，$3\le n\le 10^5$，$1\le A_i\le 10^9$。

[problemUrl]: https://atcoder.jp/contests/joi2014ho/tasks/joi2014ho3 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 君が食べることになるピースの大きさはいくらになるだろうか．

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

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

6
1
5
4
5
2
4

6

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

213

### 課題 切れ込みの個数 $ N $ と，各部分の大きさを表す整数 $ A_1,\ \ldots,\ A_N $ が与えられる．バームクーヘンを $ 3 $ つに切り分けたときの，最も小さいピースの大きさの最大値を出力するプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 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 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 !\[\](https://img.atcoder.jp/joi2014ho/2014-ho-t3-fig02.png)図 2: $ 1 $ 番目の切れ込みと $ 3 $ 番目の切れ込みと $ 5 $ 番目の切れ込みで切るのが最善である． - - - - - -