题目描述

有一根木棒，上面有 $N-1$ 道刻痕，这些刻痕把木棒分成了 $N$ 段。

从一端开始数，各段的长度依次是 $L_1, L_2, \ldots, L_N$。

现在要选择其中一道刻痕，在那里把木棒折断，得到两根木棒。请求出这两根木棒长度之差的绝对值的最小值。

其中刻痕本身的宽度忽略不计，折出来的每根木棒的长度就是它所包含的各段长度之和。

输入格式

N
L_1 L_2 ... L_N

输出格式

输出答案。

输入示例 1

4
5 2 3 8

输出示例 1

2

示例 1 说明

在每一道刻痕处折断的结果如下：

• 在从一端数第 $1$ 道刻痕折断，两根木棒长度分别为 $5$ 和 $13$，差的绝对值是 $8$；
• 在第 $2$ 道刻痕折断，长度分别为 $7$ 和 $11$，差的绝对值是 $4$；
• 在第 $3$ 道刻痕折断，长度分别为 $10$ 和 $8$，差的绝对值是 $2$。

三者取最小得到 $2$。注意刻痕只有 $N-1 = 3$ 道，不能在木棒的两端「折断」。

输入示例 2

7
31 41 59 26 53 58 97

输出示例 2

51

示例 2 说明

总长为 $365$，是奇数，所以两段不可能相等，答案至少是 $1$；实际最优的一刀落在前 $4$ 段与后 $3$ 段之间，得到 $157$ 与 $208$，差为 $51$。这说明最接近一半的分割点未必让差很小，必须每个刻痕都试一遍。

输入示例 3

10
67011 35764 33042 24098 63738 98760 17199 68579 21812 45408

输出示例 3

28105

示例 3 说明

本组数据的总长为 $475411$，接近 $N$ 与 $L_i$ 同时取较大值的情形，可用来检验前缀和是否会超出 $32$ 位整数范围（本题总长最大约 $10^7$，尚未溢出，但养成用 long long 的习惯更稳妥）。

约束条件

• $2 \le N \le 100$
• $1 \le L_i \le 10^5$
• 所有输入值均为整数