问题文

有 $N$ 张卡片，每张卡片上写着一个整数，从上到下依次为 $a_{i}$。

Alice 和 Bob 决定用这些卡片玩游戏。

两个人轮流从剩余的卡片中取一张或多张，写下所取整数的和。

当卡片都被取完后，根据写下的整数计算游戏得分。

记写下的整数的个数为 $K$，游戏的得分是第 $(K+1)/2$ 小的整数。

两个人事先知道卡片上的数字。Alice 希望尽可能使得得分最大，Bob 希望尽可能使得得分最小。

在两个人都采取最优策略的情况下，游戏的得分是多少？

约束条件

• $1 \leq N \leq 1000$
• $0 \leq |a_i| \leq 10^9$
• 所有输入均为整数

输入

输入从标准输入中获取，并具有以下格式。

$N$

$a_1$ $a_2$ ... $a_{N-1}$ $a_N$

输出

输出游戏的得分，即两个人采取最优策略后得到的结果。

示例 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

在两个人都采取最优策略的情况下，得分为 $8$。