题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,\dots,a_n$，请找一个切割点，将它分成前后两部分，使得这两部分的和相差最小。输出这个最小的差值。

输入格式

• 第一行，单个整数 $n$
• 第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$

输出格式

• 单个整数：表示两个子串总和之差的最小值。

数据范围

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

样例数据

输入:

3
100 1 1

输出:

98

说明:

100-(1+1)

输入:

6
1 2 3 4 5 6

输出:

1

说明:

(5+6)-(1+2+3+4)