正の長さを持つ $n$ 個の部分からなる折りたたみ棒があります。各部分はヒンジ（伸縮するひも）で接続されており、各ヒンジで 180 度折りたためます。一つ以上のヒンジで折りたたんだ後の棒の長さを包装長と呼びます。折りたたみ方によって包装長は異なる場合があります。

棒を次の方法で折りたたむという条件のもとで、最小の包装長を求めてください。最初に棒の各部分を水平な直線上に置きます。その後、左から右へ時計回りに棒を折りたたみます。折りたたむ際、各ヒンジの左側につながる部分は、時計回りに 180 度回転するか、まったく回転しません。

例えば下図は、各部分の長さの合計が $10$ の四つの部分からなる棒です。図では、各部分の長さは左から $3,2,2,3$ で、ヒンジは ①, ②, ③ で示されています。

この例ではヒンジ ① と ② の両方で折りたたむことはできません。① で折りたたんでから ② で折りたたむと、ヒンジ ② をまたぐ長さ $3$ の部分が折れてしまうためです。② だけで折りたたむと包装長は $5$ です。① と ③ で順に折りたたむと、下図のように包装長は $4$ です。

折りたたみ棒の各部分の長さの列が与えられます。棒の最小の包装長を出力するプログラムを書いてください。

入力

プログラムは標準入力から読み込んでください。入力は、棒の部分の数を表す整数 $n$ ($2\le n\le100000$) を含む行から始まります。次の行には、棒の左端から右端までの部分の長さを順に表す $n$ 個の正の整数が含まれます。各部分の長さは $20000$ 以下です。

出力

プログラムは標準出力に書き込んでください。ちょうど一行に、最小の包装長を表す正の整数を出力してください。

次に三つのテストケースの入力例と出力例を示します。

入出力例

入力 1

4
3 2 2 3

出力 1

4

入力 2

5
1 1 1 1 1

出力 2

1

入力 3

7
1 3 2 3 4 2 2

出力 3

6