题目描述

我们有 $N$ 个重量，编号从 $1$ 到 $N$。重量$i$的质量为 $W_i$。

我们将这些重量分成两组:索引不大于 $T$ 的重量和索引大于 $T$ 的重量，其中$1 \leq T < N$。

令 $S_1$为前一组重量的质量总和，$S_2$为后一组重量的质量总和。

考虑所有可能的分组方式，找出 $S_1$和 $S_2$,的最小可能的绝对差(差的绝对值)。

输入

第一行一个整数$N$,表示物品的个数

接下来一行共$N$个整数,分别表示第$i$个物品的重量。

输出

输出 $S_1$和 $S_2$的最小可能的绝对差。

3
1 2 3

0

样例解释

若$T=2$，则$S_1=1+2=3$，$S_2= 3$，最小的绝对差为 0。

4
1 3 1 1

2

样例解释

若$T=2$，则$S_1=1+3=4$，$S_2=1+1 =2$，最小的绝对差为 2。无法找到更小的绝对差

8
27 23 76 2 3 5 62 52

2

提示

$2 \leq N \leq 100$

$1 \leq W_i \leq 100$