You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

我于她可有可无.还是没能读懂她.别再让我心动了

题目描述

x 和 y 吵架了，他们现在要用一场游戏来分胜负。

给定长度为偶数 n 的数组，x 先选一个数，之后 y 再选，依次进行。

但是 y 非常溺爱 x ，给了 x 一个特权： y 选的数字必须小于 x 刚刚选的(这是 x 选数就有了个限制条件，他不能选仅有一个的最小的数，因为她不能让 y 无数可选)。 但是，x不能把y逼急了，x如果选的数字让y无法选了，y就可以随便选数字(比如x选了最小的数字，y就没法选了，那么y就可以随便选)。

现在有个总积分，初始为0，

每次 x 选择的数字加到总积分上，y 选的数字被减到总积分上。

x 想让总积分变得最大，y 想让总积分变得最小。

问两人都选取最优解的情况下，所有数字选完后积分为多少。

输入描述

第一行输入一个偶数 n (2 <= n <= 10⁶ ) 表示数字的数量。

第二行输入 n 个正整数 a_i (1 <= a_i <= 10⁹ ) 表示数字的大小。

输出描述

输出最后的积分

样例

6
1 2 3 4 5 6

9