当前没有测试数据。

题目描述

给定 $n$ 个正整数 $a_1, a_2, ..., a_n$，你需要将这 $n$ 个数分成两组（可以有组为空），使得两组元素之和的差的绝对值最小。

更形式化地，设两组的元素和分别为 $S_1$ 和 $S_2$，你需要最小化 $|S_1 - S_2|$。

请输出这个最小的差的绝对值。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$。

输出格式

输出一个整数，表示两组元素之和的最小差的绝对值。

样例 #1

输入

4
1 2 3 4

输出

0

样例 #2

输入

5
1 9 2 3 8

输出

1

样例说明

样例 1 解释

可以将 $1, 4$ 分成一组（和为 $5$），$2, 3$ 分成另一组（和为 $5$），差为 $0$。

样例 2 解释

可以将 $1, 9$ 分成一组（和为 $10$），$2, 3, 8$ 分成另一组（和为 $13$），差为 $3$。或者 $9, 2$ 分成一组（和为 $11$），$1, 3, 8$ 分成另一组（和为 $12$），差为 $1$。

数据范围

对于 $30\%$ 的数据，$1 \le n \le 20$。

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le a_i \le 1000$。