1483: 最小和

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:14 解决:10

题目描述

N个数排成一排,你可以任意选择连续的若干个数,算出它们的和。问该如何选择才能使得和的绝对值最小。

如:N=8时,8个数如下:

1    2    3    4    5    6    7    8

-20   90  -30   -20   80  -70  -60   125

如果我们选择144个数,和为20,还可以选择683个数,和为-5|-5|=5,该方案获得的和的绝对值最小。

输入

第一行输入N,表示数字的个数。接下来N行描述这N个数字。

输出

第一行输出一个整数,表示最小绝对值的和,第二行包含两个整数表示形成该绝对值和最长序列的长度。

样例输入 复制

8
-20
90
-30
-20
80
-70
-60
125

样例输出 复制

5
3

提示

数据说明:

40%的数据 N<=4000

对于许多数据,最长序列的长度唯一。

100%的数据 N<=100000,|每个数字的值|<=10^10