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

题目描述

徐老师和黄老师最近在学习博弈问题，他们认识了两个非常聪明的小朋友 $Alice$ 和 $Bob$

于是他们决定给他俩出一个新的博弈游戏《战国将领》

这个游戏是这样的，徐老师会挑出 $n$ 个 将军棋子 编号 $1 \sim n$，其中第 $i$ 个 将军棋子 的战斗力为 $a_i$（$a_i$可能是负数，即表示内奸）

每局游戏需要一名玩家作为 领主，一名玩家作为 攻城者 ，由 领主 先开始选棋子，从剩余棋子中选择一个棋子加入己方阵营，两人交替进行，直到所有棋子被选完（每轮不能不选棋子）

记 领主 所选棋子的战斗力总和为 $sum_A$，攻城者 所选棋子的战斗力总和为 $sum_B$

那么最终 领主 的得分为 $ans = |sum_A| - |sum_B|$

显然，领主 希望得分尽可能高，而 攻城者 希望得分尽可能低。

现在徐老师任命 $Alice$ 来当 领主， $Bob$ 当 攻城者，他想知道如果两人都足够聪明，采取最优策略的情况下，$Alice$ 的得分会是多少？

输入格式

第一行包含一个整数 $n$

第二行包含 $n$ 个整数，分别为 $a_1,a_2,...,a_n$，依次表示每个 将军棋子 的战斗力

输出格式

输出一行包含一个整数，表示 $Alice$ 的最终得分

数据范围

对于所有数据保证：$|a_i| \le 10^9$。

样例输入1

6
6 -1 -6 -1 4 -3

样例输出1

1

样例解释1

两人的选择情况依次如下

1. $Alice$ 选 $-6$ 的棋子
2. $Bob$ 选 $-3$ 的棋子
3. $Alice$ 选 $-1$ 的棋子
4. $Bob$ 选 $-1$ 的棋子
5. $Alice$ 选 $4$ 的棋子
6. $Bob$ 选 $6$ 的棋子

$sum_A=-6-1+4=-3,sum_B=-3-1+6=2$

最终得分为 $|-3|-|2|=1$

样例输入2

10
3 -1 -7 -2 4 -5 -9 7 2 10 

样例输出2

2