题目描述

We have $N$ weights indexed $1$ to $N$. The mass of the weight indexed $i$ is $W_i$.

We will divide these weights into two groups: the weights with indices not greater than $T$, and those with indices greater than $T$, for some integer $1 \leq T \lt N$. Let $S_1$ be the sum of the masses of the weights in the former group, and $S_2$ be the sum of the masses of the weights in the latter group.

Consider all possible such divisions and find the minimum possible absolute difference of $S_1$ and $S_2$.

我们有 $N$ 个砝码，索引号为 $1$ 至 $N$ 。索引为 $i$ 的砝码的质量为 $W_i$ 。

我们将把这些权重分为两组：索引不大于 $T$ 的权重和索引大于 $T$ 的权重，其整数为 $1 \leq T \lt N$ 。设 $S_1$ 为前一组砝码的质量总和， $S_2$ 为后一组砝码的质量总和。

考虑所有可能的分割，求出 $S_1$ 和 $S_2$ 的最小绝对差。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $S_1$ 和 $S_2$ 的最小绝对差值。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

0

样例 #2

样例输入 #2

4
1 3 1 1

样例输出 #2

2

样例 #3

样例输入 #3

8
27 23 76 2 3 5 62 52

样例输出 #3

2

说明

数据规模与约定

• $2 \leq N \leq 100$
• $1 \leq W_i \leq 100$
• 所有输入值均为整数。

样例 $1$ 解释

如果 $T = 2$ 、 $S_1 = 1 + 2 = 3$ 和 $S_2 = 3$ ，绝对差值为 $0$ 。

样例 $2$ 解释

如果 $T = 2$ 、 $S_1 = 1 + 3 = 4$ 和 $S_2 = 1 + 1 = 2$ ，绝对差为 $2$ 。我们不可能有更小的绝对差值。