AT_code_thanks_festival_2018_h Median Game

[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2018/tasks/code_thanks_festival_2018_h 整数が $ 1 $ つずつ書かれたカードが $ N $ 枚積んであり、上から $ i $ 枚目には $ a_{i} $ が書かれています。 AliceとBobはこのカードを使ってゲームを行うことにしました。 $ 2 $ 人はAliceから始めて交互に、残っているカードを上から $ 1 $ 枚以上好きなだけ取り、この時取った整数の和を書き出します。 カードが無くなるとこのゲームのスコアを、書き出された整数を用いて計算します。 書き出された整数の個数を $ K $ 個とした時、小さい方から $ (K+1)/2 $ 以上の最小の整数 番目の値がこのゲームのスコアです。 $ 2 $ 人はカードに書かれている数を事前に知っています。Aliceはゲームのスコアを出来るだけ大きく、Bobは小さくしたいです。 $ 2 $ 人がそれぞれ最善に振る舞った時、このゲームのスコアはいくつになるでしょうか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ ... $ a_{N-1} $ $ a_N $

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

### 制約 - $ 1\ \leq\ N\ \leq\ 1000 $ - $ 0\ \leq\ |a_i|\ \leq\ 10^9 $ - 入力は全て整数である ### Sample Explanation 1 Aliceが初めに $ \{1,\ -1\} $ を取ると、書かれる整数は $ \{0\} $ で、スコアは $ 0 $ になります。 Aliceが初めに $ \{1\} $ を取ると、Bobは $ \{-1\} $ を取ることになり、書かれる整数は $ \{1,\ -1\} $ で、スコアは $ 1 $ になります。 よってAliceにとっては $ \{1\} $ を取る方が良く、スコアは $ 1 $ となります。