AT_code_thanks_festival_2018_h Median Game

有 $N$ 张卡片，每张卡片上写有一个整数，从上到下第 $i$ 张卡片上写有 $a_i$。 Alice 和 Bob 决定用这些卡片进行游戏。 两人轮流行动，从 Alice 开始，每次可以从剩下的卡片堆顶取走至少 $1$ 张任意数量的卡片，并将本次取走的卡片上的整数之和记录下来。 当所有卡片都被取完后，游戏结束。此时，将所有记录下来的整数记为 $K$ 个，记它们从小到大排序后的第 $\lceil \frac{K+1}{2} \rceil$ 小的数为本局游戏的得分。 两人都事先知道所有卡片上的数字。Alice 希望让游戏得分尽可能大，Bob 希望让得分尽可能小。 当两人都采取最优策略时，游戏的得分是多少？

输入以以下格式从标准输入读入。 > $N$ $a_1$ $a_2$ ... $a_{N-1}$ $a_N$

输出当两人都采取最优策略时，游戏的得分。

### 限制条件 - $1 \leq N \leq 1000$ - $0 \leq |a_i| \leq 10^9$ - 输入均为整数 ### 样例解释 1 如果 Alice 一开始取 $\{1, -1\}$，则记录的整数为 $\{0\}$，得分为 $0$。如果 Alice 一开始只取 $\{1\}$，则 Bob 只能取 $\{-1\}$，记录的整数为 $\{1, -1\}$，得分为 $1$。因此对 Alice 来说，取 $\{1\}$ 更优，得分为 $1$。 由 ChatGPT 4.1 翻译