题目描述

现在有 $n$ 个苹果，苹果的重量分别为 $a_1, a_2, \cdots, a_n$。你的任务是将苹果分成两堆，使得两堆苹果的重量和的差值最小。

输入格式

第一行输入一个正整数 $n$ 表示苹果数量。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 表示每一个苹果的重量。

输出格式

输出一行一个整数表示最小的重量差值。

样例

5
3 2 7 4 1

1

提示

可以分成重量为 $(2, 3, 4)$ 和 $(1, 7)$ 的两堆，这样重量和的差值为 $(2 + 3 + 4) - (1 + 7) = 1$，可以证明这种划分方式重量和的差值是最小的。

数据范围

• $1 \le n \le 20$
• $1 \le a_i \le 10^9$