拔河

题目描述

update(25/04/05)本题新增一组hack数据。

小明是学校里的一名老师，他带的班级共有 $n$ 名同学，第 $i$ 名同学力量值为 $a_i$。在闲暇之余，小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近，需要在这 $n$ 名同学中挑选出两个队伍，队伍内的同学编号连续:{$a_{l1}, a_{l1+1}, ..., a_{r1−1}, a_{r1}$} 和{$a_{l2}, a_{l2+1}, ..., a_{r2−1}, a_{r2}$}，其中 $l_1 ≤ r_1 < l_2 ≤ r_2$。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式

输入共两行。

第一行为一个正整数 $n$。

第二行为 $n$ 个正整数 $a_i$。

输出格式

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

样例 #1

样例输入 #1

5
10 9 8 12 14

样例输出 #1

1

提示

【样例说明】

其中一种最优选择方式：队伍 $1$：${a_1, a_2, a_3}$，队伍 $2$：${a_4, a_5}$，力量值和分别为 $10 + 9 + 8 = 27，12 + 14 = 26$，差距为 $|27 − 26|$ $= 1$。

【评测用例规模与约定】

对于 $20\%$的评测用例，保证 $n ≤ 50$。

对于 $100\%$ 的评测用例，保证 $n ≤ 10^3，a_i ≤ 10^9$。