配点 : $700$ 点

問題文

$N$ 個の整数 $A_1$, $A_2$, ..., $A_N$ が与えられます。

$A$ のすべての空でない部分列について、それぞれの和を考えます。このような和は $2^N - 1$ 個存在し、この個数は奇数です。

これらの和を昇順に並べたものを $S_1$, $S_2$, ..., $S_{2^N - 1}$ とします。

これらの中央値、$S_{2^{N-1}}$ を求めてください。

制約

• $1 \leq N \leq 2000$
• $1 \leq A_i \leq 2000$
• 入力値はすべて整数である。

入力

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

$N$

$A_1$ $A_2$ $...$ $A_N$

出力

$A$ のすべての空でない部分列の和を書き並べてソートした際の中央値を出力せよ。

3
1 2 1

2

この場合、$S = (1, 1, 2, 2, 3, 3, 4)$ となり、中央値は $S_4 = 2$ です。

1
58

58

この場合、$S = (58)$ となります。