H - Median Game

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

整数が 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