题目描述

Y 同学有 $N$ 块砝码，第 $i$ 块重量为 $A_i$。他要把所有砝码分到左右两个托盘中，每块砝码必须且只能放入一个托盘。

请你求出两个托盘总重量差的最小可能值。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,\dots,A_N$。

输出格式

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

样例

样例输入 #1

5
3 1 4 2 2

样例输出 #1

0

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le N\le5000$，$1\le A_i\le1000$，且 $\sum A_i\le2\times10^5$。

特殊性质 A：保证所有 $A_i$ 相等。

特殊性质 B：保证 $A_i\le10$。