J君は妹のO子ちゃんとI子ちゃんと一緒におやつを食べようとしている。今日のおやつは3人の大好物のバームクーヘンだ。 バームクーヘンは右図のような円筒形のお菓子である。3人に分けるために、J君は半径方向に刃を3回入れて、これを3つのピースに切り分けなければならない。
　このバームクーヘンにはあらかじめN個の切れ込みが入っており、J君は切れ込みのある位置でのみ切ることができる。切れ込みに1からNまで時計回りに番号をふったとき、1 ≦i ≦ N－1に対し、i番目の切れ込みとi +1番目の切れ込みの間の部分の大きさはAi である。またN番目の切れ込みと1番目の切れ込みの間の部分の大きさはANである。
　妹思いのJ君は、バームクーヘンを3つのピースに切り分けたあと、自分は最も小さいピースを選び、残りの2つのピースを2人の妹にあげることにした。一方で、J君はバームクーヘンが大好物なので、できるだけたくさん食べたいと思っている。最も小さいピースの大きさが最大になるように切ったとき、J君が食べることになるピースの大きさはいくらになるだろうか。

課題

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

入力

標準入力から以下のデータを読み込め。
・ 1行目には、整数N が書かれている。これはバームクーヘンにN個の切れ込みがあることを表す。
・ 続くN 行のうちのi 行目（1≦i ≦N）には、整数Aiが書かれている。これはi番目の切れ込みとi + 1番目の切れ込みの間の部分（i = NのときはN番目の切れ込みと1番目の切れ込みの間の部分）の大きさがAiであることを表す。

出力

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

制限

すべての入力データは以下の条件を満たす。
・ 3≦N≦100 000
・ 1≦Ai ≦1 000 000 000 （1≦i≦N）。

情報オリンピック日本委員会 作 『第13回日本情報オリンピック JOI 2013/2014 本選競技課題』はクリエイティブ・コモンズ 表示- 継承 4.0 国際ライセンスで提供されています。

解説

［愚直な解法］

　切れ込みの入れ方を全て試し、各部分の大きさを計算し、最も小さい部分が最も大きくなるものを調べるというアルゴリズムが考えられます。切れ込みの入れ方がO （N3）^［1］通りあり、各部分の大きさの計算にO （N）時間かかるので、全体でO（N4）時間必要となります。この方法により確かに正しい答えを得られますが、制限時間内にはN ≦ 100 程度までしか扱うことができず、満点は得られません。

［満点解法］

　答えを直接求めるのではなく、「答えがk 以上か？」という判定をすることを考えます。この判定ができると、次のような「二分探索」と呼ばれる手法により答えを求めることができます。

　今、答えがa 以上b未満であるとわかっているします。b = a+1 であれば、答えはa と判明します。そうでない場合はk = （a+b）/2（小数点以下は切り下げ）とおいて、答えがk 以上かを判定します。もしk以上であれば答えはk 以上b 未満であるとわかり、k 以上でなければa 以上k 未満であるとわかります。1 回の判定で答えの範囲を半分に絞り込むことができ、最初は答えの範囲は1 以上、S = 109 ×N以下であるとわかっているため、 log2 S ≦50 回程度の判定を行うことで答えを求めることができます。

　「答えがk以上か？」の判定は、次の考察を活用するとO （N）もしくはO （N log N）の時間で行うことができ、二分探索と合わせて満点を取ることが可能となります。詳細については各自考えてみてください。

考察：ある切れ込みで切ったとすると、次は大きさがk以上となる最初の切れ込みで切ればよい。

　「二分探索」はソートされた列から要素を検索するなどの用途で、さまざまなプログラミング言語の標準ライブラリの内部で使われており、二分探索を知らない人でもそういった効率的なアルゴリズムを利用することが可能です。しかし、二分探索をしっかりと理解していれば、この問題のように多様な場面で応用が可能になります。

解説文作成： 吉田悠一 情報学プリンシプル研究系 准教授
　　　　　　岩田陽一 情報学プリンシプル研究系 助教

［1］「オーダーN3 乗」と読み、ある大きな数C > 0に対してCN3以下という意味です。例えば100N3や10000N3などを略記するために使われます。O（N）やO（N2）も同様に定義されます。