题目描述

某工厂有一条传送带，上面依次摆放着 $N$ 箱物资，第 $i$ 箱物资的重量为 $W_i$。

现在需要将这些物资分配到两辆运输车上。规定：

• 第一辆车装载传送带前面从第 $1$ 箱开始的连续的一部分物资。
• 第二辆车装载剩余所有的物资。
• 两辆车都必须至少装载一箱物资。

设分割位置为整数 $k$（$1 \le k < N$），则：

• 第一辆车装载第 $1$ 至第 $k$ 箱物资。
• 第二辆车装载第 $k+1$ 至第 $N$ 箱物资。

分别记两辆车装载的总重量为 $S_1$ 和 $S_2$。为了保证运输安全，希望两辆车的载重尽可能接近。请你计算在所有合法分割方式中，$|S_1 - S_2|$ 的最小值。

备注：绝对值 $|x|$ 表示 $x$ 到 $0$ 的距离，例如 $|3|=3$，$|-3|=3$，$|0|=0$。

输入格式

第一行输入一个整数 $N$，表示物资的箱数。 第二行输入 $N$ 个整数 $W_1,W_2,\dots,W_N$，代表每箱物资的重量。

输出格式

输出一个整数，表示两辆车载重差的绝对值的最小可能值。

样例 #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

说明

样例 1 说明

当分割位置 $k = 2$ 时：

• 第一辆车总重量 $S_1 = 1 + 2 = 3$。
• 第二辆车总重量 $S_2 = 3$。 此时 $|S_1 - S_2| = 0$，达到最优。

样例 2 说明

当分割位置 $k = 2$ 时：

• 第一辆车总重量 $S_1 = 1 + 3 = 4$。
• 第二辆车总重量 $S_2 = 1 + 1 = 2$。 差值为 $2$，无法取得更小值，因此答案为 $2$。

数据范围

对于 $100\%$ 的数据，满足 $2 \le N \le 100$，$1 \le W_i \le 100$。