小紫的劣势博弈
时间限制: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 的值是多少?

输入描述:

\hspace{15pt}第一行输入一个正整数 n \left(1 \leqq n \leqq 10^5\right) 代表数组中的元素数量。 
\hspace{15pt}第二行输入 n 个正整数 a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^9\right) 代表数组中的元素。

输出描述:

\hspace{15pt}一个整数,代表最终 x 的值。
示例1

输入

复制
3
2 3 4

输出

复制
3

说明

\hspace{15pt}在这组样例中,过程如下:
\hspace{23pt}\bullet\,小红先手操作,拿走 2x = 2
\hspace{23pt}\bullet\,小紫拿走 3x = -1
\hspace{23pt}\bullet\,小红拿走 4x = 3
\hspace{15pt}因此,最终 x = 3