#P86. 挑选球员

挑选球员

题目描述

有n个球员,现在要把他们分成两队,让他们打比赛。每个人都有一个技巧值,有两个教练, 教练A和教练B, 这两个教练轮流挑选球员,这两个教练每次都是从当前剩下的球员中挑选技巧值最大的球员。第一次是教练A先挑选。当教练A和教练B挑完球员后,问:教练A挑选的球员的技巧总和比教练B挑选的球员的技巧总和大多少? 例如:有5个球员,技巧值分别是:{5,7,8,4,2}, 那么教练A先选8,教练B选7,教练A选5,教练B旋4,教练A选2. 最后教练A选到的总和是:15,教练B选到的总和是:11, 所以你应该输出4。

输入格式

第一行:一个整数n, 1 <= n <= 50 第二行: n个非负整数,第i个整数表示第i个球员的技巧值, 技巧值不超过10000。

输出格式

一行:一个整数,教练A挑选的球员的技巧总和比教练B挑选的球员的技巧总和大多少?

样例

input

4 
9  8  7  6

output

2

限制与提示

时间限制:1s1 \text {s}

OJ稀有题

开放时间1h