题目描述

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

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

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

输入格式

输入共两行。 第一行为一个正整数 n。 第二行为 n 个正整数 a[1], a[2], …, a[n]。

输出格式

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

输入输出样例 #1

输入 #1

5
10 9 8 12 14

输出 #1

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。
• 对 80% 的数据，n ≤ 100。
• 对全部的测试数据，保证 1 ≤ n ≤ 10^3，1 ≤ a[i] ≤ 10^9。