题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,\ldots ,a_n$，请选取一个切割点，将序列分成前、后两部分，使得这两部分元素和的差值 尽可能小。输出这个最小差值。

输入格式

• 第一行：一个整数 $n$（$1 \le n \le 100000$）
• 第二行：$n$ 个整数 $a_1,a_2,\ldots ,a_n$（$1 \le a_i \le 10000$）

输出格式

• 一个整数：表示两部分元素和之差的最小值。

数据范围

• 对于 $30\%$ 的数据：$1 \le n \le 100$
• 对于 $70\%$ 的数据：$1 \le n \le 10000$
• 对于 $100\%$ 的数据：$1 \le n \le 100000$
• $1 \le a_i \le 10000$

3
100 1 1

98

说明：100-(1+1)

6
1 2 3 4 5 6

1

说明：(5+6)-(1+2+3+4)