問題文

整数が $1$ つずつ書かれたカードが $N$ 枚積んであり、上から $i$ 枚目には $a_{i}$ が書かれています。

AliceとBobはこのカードを使ってゲームを行うことにしました。

$2$ 人はAliceから始めて交互に、残っているカードを上から $1$ 枚以上好きなだけ取り、この時取った整数の和を書き出します。

カードが無くなるとこのゲームのスコアを、書き出された整数を用いて計算します。

書き出された整数の個数を $K$ 個とした時、小さい方から $(K+1)/2$ 以上の最小の整数 番目の値がこのゲームのスコアです。

$2$ 人はカードに書かれている数を事前に知っています。Aliceはゲームのスコアを出来るだけ大きく、Bobは小さくしたいです。

$2$ 人がそれぞれ最善に振る舞った時、このゲームのスコアはいくつになるでしょうか。

制約

• $1 \\leq N \\leq 1000$
• $0 \\leq |a_i| \\leq 10^9$
• 入力は全て整数である

入力

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

$N$ $a_1$ $a_2$ ... $a_{N-1}$ $a_N$

出力

$2$ 人が最善の取り方をした場合の、ゲームのスコアを出力せよ。

入力例 1

2
1 -1

出力例 1

1

Aliceが初めに $\\{1, -1\\}$ を取ると、書かれる整数は $\\{0\\}$ で、スコアは $0$ になります。 Aliceが初めに $\\{1\\}$ を取ると、Bobは $\\{-1\\}$ を取ることになり、書かれる整数は $\\{1, -1\\}$ で、スコアは $1$ になります。

よってAliceにとっては $\\{1\\}$ を取る方が良く、スコアは $1$ となります。

入力例 2

3
3 1 4

出力例 2

8