问题 12 捡石头 III 提交列表 提交

普及+/提高 · stoneIII.in 复制 · stoneIII.out 复制 · 0:00:01 · https://oj.wtf/12  复制分享链接 

描述

前几天在捡石头II中,小明在你的帮助下,运用动态规划算法见到了很多的石头。他的好朋友小红非常羡慕,于是她开始了捡石头III

小红去海边的沙滩上玩,发现了N颗石头。所有石头都是一样重量,而它们的价值不同。第i颗石头的价值是v[i],所有石头在沙滩上排成一排。 小红不喜欢走路,因此这条海岸线她只会走一遍。她身上带了两个盒子, 由于她只会走一遍,她只能取走两个区间的石头。此外,小红希望两个盒子的大小相同。 现在,她希望两个区间的石头价值之和的差的绝对值尽量小。小红绝不会空手而归,所以她会至少取走两颗石头

样例解释1: 小红有很多种方法取到0,比如5-6和9-10

样例解释2: 选择1-2和5-6两个区间,差是 19292。

数据范围: 40%的数据满足N<=100 100%的数据满足N<=1000,v[i]<=10^15

输入

第一行个正整数N,表示石头总数。第二行N个正整数,第i个表示v[i],即石头的价值。

输出

一行一个整数表示石头的价值之差的绝对值的最小值

样例

输入

11
8 12 2 4 3 15 5 1 6 11 7

输出

0

输入

8
103928 492239 139233 547863 227643 349232 72193 424939

输出

19292