B-小紫的劣势博弈_牛客周赛 Round 85

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 有一个由 $n$ 个整数构成的数组 $\{a_1, a_2, \dots, a_n\}$ 和一个整数 $x = 0$ 。
$\hspace{15pt}$ 小红和小紫轮流操作，每次操作方拿走数组中的一个元素，并从数组中移除。
$\hspace{15pt}$ 记被拿走的元素为数组中的第 $i$ 个元素 $a_i$ ，若是小红拿走的，则会让 $x$ 加上 $a_i$ ；若是小紫拿走的，则会让 $x$ 减去 $a_i$ 。
$\hspace{15pt}$ 小红希望最终 $x$ 尽可能小，小紫希望最终 $x$ 尽可能大。
$\hspace{15pt}$ 小红先手操作，请问双方都采用最优策略时，最终 $x$ 的值是多少？

输入描述:

第一行输入一个正整数  代表数组中的元素数量。 
第二行输入  个正整数  代表数组中的元素。

输出描述:

一个整数，代表最终  的值。

示例1

输入

复制

3
2 3 4

输出

复制

说明

在这组样例中，过程如下：
小红先手操作，拿走 ，；
小紫拿走 ，；
小红拿走 ，。
因此，最终 。