说明

小明的班级在上体育课，老师想让大家分成两组玩拔河。现在大家排成了一排，老师嫌麻烦，所以想直接在队伍中间找个位置断开，这样不就分成了两组了吗？但是这个老师的思维很奇怪，他觉得分成人数相等的两组会不公平，他想让两组的体重和的差最小（差值要求体重和大的值减小的值）。老师把这个任务交给了小明，你能帮帮他吗？

输入格式

第一行为一个正整数n，表示小明班的人数。

第二行为n个正整数，表示这一排从左到右同学的体重。

输出格式

只有一行，为题目描述中最小的差值。

样例

5
11 17 3 2 20 

3

提示

从第二位和第三位同学中间断开，则

第一位和第二位同学分为一组，体重和为11+17=28

第三位，第四位和第五位分为一组，体重和为3+2+20=25

28和25相差3，此时为最小，所以答案为3。

数据规模

60%的数据：2<=n<=1000，每个同学的体重不超过20。

100%的数据：2<=n<=100000，每个同学的体重不超过1000。