3940 - 分蛋糕

有n块蛋糕,要分给两个人,要求分完后两个人的蛋糕重量总和的差的绝对值最小
 

比如1 2 3 4 5 分给两个人,一种合理的分法是
 

1 2 4给一个人
 

3 5给另一个人
 

这样子相差1,是最小的

输入

第一行输入一个整数n ($1 \le n \le 100$)

第二行输入n个整数$a_i$

$1 \le a_i \le 100000$

输出

输出最小差值的绝对值

样例

输入

5
1 2 3 4 5 

输出

1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题