问题 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

提示

来源

[献花][花圈]