题目背景

有 n 个物品排成一排，每个物品有重量。要沿某个位置切一刀，把物品分成左、右两拨（两拨都不能为空）。希望两拨总重量之差尽量小。

题目描述

给定 n 个物品的重量，输出把序列切成两段后，左段总重与右段总重之差的绝对值的最小值。

输入格式

第一行一个整数 n。第二行 n 个整数，表示每个物品的重量。

输出格式

一个整数，表示两段重量差绝对值的最小值。

输入输出样例

5
1 2 3 4 5

3

样例 1：切成 [1,2,3] 和 [4,5]，重量差 |6-9|=3 最小。

说明/提示

2 ≤ n ≤ 10⁵，0 ≤ 重量 ≤ 10⁵。两段都不能为空。总重量可能很大，请用 64 位整数。