题目描述

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

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

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

输入格式

第一行为一个正整数 $n$。
第二行为 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

输出格式

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

样例

5
10 9 8 12 14

1

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

数据范围

• 对于 $40\%$ 的数据：$n \le 10$。
• 对于 $100\%$ 的数据：$n \le 100$，$1 \le a_i \le 10^9$。