408567: GYM103186 J Alice and Bob-1

众所周知，Alice 和 Bob 是很好的朋友，他们总是喜欢在一起玩有趣的游戏。并且他们每个人都很争强好胜并且高智商，都想尽力赢下对方。但由于 Alice 是女生，Bob 很有绅士风度，总是会让 Alice 先手。

今天他们遇到的游戏是这样的，给定 $$$ n $$$ 张卡片，每张卡片都有一个数值。他们每个人轮流交替取走一张卡片，直到取完。

定义手中卡片的价值是所有你取得的卡片数值的和的绝对值，即假设 Alice 取走的卡为$$$\pi_1,\dots, \pi_k$$$，那么她所拥有的价值为 $$$A=\left |\sum\limits_{j=1}^k a_{\pi_j}\right |$$$，Bob 所拥有的价值为 $$$B=\left |\sum\limits_{i=1}^n a_i - \sum\limits_{j=1}^k a_{\pi_j}\right |$$$。

Alice 想让她取得的卡片的价值相比于 Bob 所取得的尽可能大，而 Bob 不想被 Alice 拉开差距，即 Alice 希望最终 $$$A-B$$$ 的值尽可能地大，而 Bob 希望这个值尽可能地小。

他们都想知道，在他们都采取最优策略的情况下，最终 Alice 所取得的卡片价值和 Bob 所取得的卡片价值的差会是多少？

第一行有一个整数 $$$ n $$$ ($$$ 1 \leq n \leq 5000 $$$)，表示卡片的数量。

第二行有 $$$ n $$$ 个整数 $$$a_1, a_2,\cdots,a_n$$$($$$-10^9 \leq a_i \leq 10^9$$$)，中间以空格分隔，分别表示第 $$$i$$$ 张卡片上的数值为 $$$a_i$$$ 。

在一行输出一个整数，代表最终 Alice 所取得的卡片价值和 Bob 所取得的卡片价值的差。

1
100

100

3
4 5 1

2

6
1 2 3 4 5 6

3