题目描述

小 A 和小 B 又在通过游戏决一胜负了。

今天他们玩的游戏是这样的，小 A 拿出了 $n$ 张卡片，每张卡片上都写了一个数 $a_i$。他们每个人轮流交替取走一张卡片，直到取完，小A先取。

记小 A 取走的卡片的权值和为 $A$，小B取走的卡片的权值和为 $B$，则小 A 最终得分为 $|A|-|B|$。小 A 自然希望自己的得分最大，小 B 则希望其得分最小。

他们想知道在他们都采取最优策略的情况下，小 A 的最终得分是多少。

输入格式

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

第二行包含 $n$ 个整数，分别为 $a_1,a_2,...,a_n$ ，表示小 A 拿出的 $n$ 张卡片。

输出格式

输出一行一个整数，表示小 A 的最终得分。

样例

输入

6
6 -1 -6 -1 4 -3

输出

1

样例解释

小 A 拿了为 $-6$ 的卡片，然后小 B 拿了为 $-3$ 的卡片。

小 A 拿了为 $-1$ 的卡片，然后小 B 拿了为 $-1$ 的卡片。

小 A 拿了为 $4$ 的卡片，然后小 B 拿了为 $6$ 的卡片。

最终小 A 的得分为 $|-6-1+4|-|-3-1+6|=1$ 分

数据范围

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

$\text{A}:$ 保证对于所有的 $a_i>0$

$\text{B}:$ 保证对于所有的 $a_i<0$