Problem Statement

高橋君と青木君は長さ $N$ の数列 $S$ を用いたゲームを行う。

ゲームは高橋君の手番と青木君の手番 $1$ 回ずつからなる。

ゲームは以下の要領で行われる。

• 最初に高橋君が数列の要素のうち $1$ つに丸をつける。
• 次に青木君が数列の要素で高橋君が丸を付けなかったもののうち $1$ つに丸をつける。
• 高橋君と青木君が丸を付けた $2$ つの要素に対して、その $2$ つの要素およびそれらの間にあるすべての要素を残して、それ以外の要素をすべて削除する。残った数列を $T$ と置く。
• 数列 $T$ のうち、数列 $T$ 内で左から奇数番目の要素の合計が高橋君の得点、偶数番目の要素の合計が青木君の得点となる。

青木君は、丸を付けられる要素の中で、青木君が得点を最も多く得られる要素に丸を付ける。そのような要素が複数あるならばそれらのうち最も左側にある要素に丸を付ける。

高橋君は青木君の丸の付け方を知っている。高橋君が得られる得点として考えられる得点の最大値を求めよ。

Input

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

• $1$ 行目には、整数 $N (2≦N≦50)$ が与えられる。$N$ は数列 $S$ の要素数である。
• $2$ 行目には、$N$ 個の整数 $a_1$, $a_2$, ... , $a_N (-50≦a_i≦50, 1≦i≦N)$ が与えられる。整数 $a_i$ は数列 $S$ の左から $i$ 番目の要素を表す。

Output

高橋君が得られる得点の最大値を $1$ 行に出力せよ。

出力の末尾にも改行を入れること。