题目中有两个人轮流拿食物:
笨蛋同学正在和天才同学博弈。现在在桌子上有 n 份食物,n 为偶数。第i份食物的美味度为ai。
由笨蛋同学先手,笨蛋同学每次会拿走当前桌子上美味度最高的食物。随后,天才同学为了达成自己的目标,会从桌上剩余的食物中选择并拿走一份;两人交替行动,直至桌上无食物。
天才同学的目标是:让笨蛋同学吃到的食物总美味度与自己吃到的食物总美味度的差值尽量小(可能为负数)。天才同学绝顶聪明。
请问在两人都采取各自的策略下,这个差值最小是多少?
每个测试文件均包含多组测试数据:第一行输入一个整数 T(1≤T≤2×105),代表数据组数。
每组测试数据描述如下:
除此之外,保证单个测试文件的 n之和不超过4×105。
对于每一组测试数据,新起一行。输出一个整数,表示最小的差值。
输入
3
2
10 20
4
2 1 5 8
6
1 1 1 1 1 1
输出
10
4
0
说明
对于第一组样例: