平衡

题目描述

有编号为 $1$ 到 $N$ 的 $N$ 个砝码,编号 $i$ 的砝码重量为 $W_i$。

对于某个整数 $1 \le T \lt N$,考虑把这些砝码分成两组:编号不超过 $T$ 的砝码,和编号大于 $T$ 的砝码。设这两组的重量和分别为 $S_1, S_2$。

考虑所有这样的分法,求 $|S_1 - S_2|$ 的最小值。

输入格式

输入按以下格式从标准输入给出:

$N$
$W_1$ $W_2$ $...$ $W_{N-1}$ $W_N$

输出格式

输出 $|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 \le N \le 100$
• $1 \le W_i \le 100$
• 输入均为整数