题目描述

给定一个由 $n$ 个整数组成的数列，请将其分割成左右两部分， 要求左半部分子数列的和与右半部分子数列的和最接近，请输出这两部分子数列和的差值（取非负值）。

形式化的描述为，找到一个断点 $k$，将数组分成 $[1,k],[k+1,n]$ 两个区间，并且使得 $|\sum_{i=k+1}^n a_i-\sum_{i=1}^k a_i|$ 要最小，其中 $1\le k \le n - 1$。即需要保证左半部分和右半部分都至少有一个元素。

例如：$n = 5$，数列中的 $5$ 个整数分别是 $2、1、3、4、3$，将其分割成左右两部分，左半部分是 $2、1、3$，右半部分是 $4、 3$；此时两部分子数列的和最接近，差值为 $1$。

输入格式

第一行输入一个整数 $n$（$2≤n≤100000$）。 第二行输入 $n$ 个整数（$1≤整数≤1000$），整数之间以一个空格隔开。

输出格式

输出一个整数，表示这两部分子数列和的差值（取非负值）。

5
2 1 3 4 3

1

Hint

【数据范围】

对于 $50\%$ 的数据，$2\le n \le 10^3, 1\le 整数 \le 10^3$， 对于 $100\%$ 的数据，$2\le n \le 10^5，1\le 整数 \le 10^3$