← 返回比赛
已结束 GESP欢乐赛 #3
← 上一题 下一题 →

A1421 | 艺术作品嗯分

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有两条狗艺术家共同绘制了一批画，本来打算把这些画卖成钱再分，但是他们闹矛盾了，准备分道扬镳。

画也来不及卖了，决定分掉。每幅画都有一个对应价值，这两条狗艺术家表现出艺术家嘴脸，谁都不想吃亏，所以他们按照一定的顺序来分。

首先，一条狗艺术家会拿走这幅画里价值最大的那幅画，然后另一条狗艺术字拿走剩下里面价值第二大和第三大的画；再换先拿的那条狗艺术家拿价值第四大和第五大的画……重复这个过程，直到没有画可拿。如果最后一轮中，剩下的画只有一幅，则轮到的那条狗艺术家只拿这一幅。

现在，一共有 $N$ 幅画，两条狗艺术家又吵起来了，因为他们不知道这样分完后谁赚谁吃亏，所以他们找到AC狗，请AC狗来计算按照这样的方式分组后，两组画价值之和的差的绝对值。虽然AC狗智商比肩带树，但是他不会算，请你帮他计算这个问题。

输入格式

输入的第一行为整数$N$，代表有$N$幅画。

接下来一行共$N$个整数，代表每幅画的价值。

输出格式

输出为一个非负数，代表按照这样的分组后，两组画价值之和的差的绝对值。

输入输出样例

输入 #1
5
1 2 3 4 5
输出 #1
1
输入 #2
6
1 5 8 13 14 20
输出 #2
5
C++ 编辑器
输入
输出