问题 23770 --QiQi and Game

23770: QiQi and Game

时间限制: 2 Sec  内存限制: 128 MB
提交: 41  解决: 15
[提交][状态][讨论版][命题人:]

题目描述

给你一组数,每个数有个权值,现在SmallQiQi和BigQiQi轮流取这些数,每次可以取若干个数,得分是这些数的最小值,直到取完位置,现在问双方都像fu神一样聪明的情况下,先手对后手的最大分差是多少。

输入

输入一个数n表示有n个数,接下来输入n个数。1 <= n <= 1000000,每个数 <= 1000000000。

输出

输出一个数,表示最大分差。

样例输入

3
1 3 1

样例输出

2

来源

 

[提交][状态]