该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制： 1s

空间限制： 512MB

Alice 与 Bob 希望玩一个游戏：他们首先在黑板上写下了 $n$ 个整数 $a_1,a_2,⋯,a_n$ 。

然后 Alice 与 Bob 轮流行动，Alice 先手。

当轮到 Alice 行动时，Alice 需要选择黑板上的若干整数 (至少一个) ，并从黑板上擦除这些整数。

当轮到 Bob 行动时，Bob 需要选择黑板上的一个整数，并从黑板上擦除这个数。

当一名玩家行动后，若黑板上所有数均被擦除，游戏终止。

游戏的得分被定义为 Alice 每一轮行动中所有选择的数的和。Alice 希望最大化游戏的得分，Bob 希望最小化游戏的得分。

Alice 与 Bob 均绝顶聪明，他们会以最优的策略行动。你的任务是预测这个游戏的得分。

输入格式

第一行一个正整数 $n$ 。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。

输出格式

输出一个数，表示最终游戏的得分。

样例 1

输入

5
7 10 -5 -2 -4

输出

13

样例解释 1

最优策略的游戏流程如下：

Alice 选择 $\{7,10\}$

Bob 选择 $−2$

Alice 选择 ${−4}$

Bob 选择 $−5$

游戏的得分为 $7+10+(−4)=13$

样例 2

输入

5
-6 -2 10 -7 -9

输出

1

样例 3

见下发文件 game3.in/out.

数据范围

对于 $100\%$ 的数据，保证 $1\leq n \leq 10^5,−10^9 \leq a_i \leq 10^9$ 。

具体数据范围见下表：