問題文

整数が 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
• 入力は全て整数である

入力例 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