#P1073. 砸金蛋

砸金蛋

题目描述

Mike获得一个特技,“透视”,即不用打开箱子,就能看到箱子里有什么。于是他去参加砸金蛋的游戏,一根绳子上依序挂着n个金蛋,每个金蛋内有一个纸条,上面写了一个整数作为奖励,游戏参与者可以且仅可以选择绳子上的连续的一串金蛋,比如第二号到第五号。Mike利用特异功能已经先看到了所有金蛋内的纸条上的数值,请你帮他编写一个程序,找到一个起点和终点,使得Mike获得的奖励值最大。

输入格式

输入格式 第一行输入一个正整数; 第二行有n个整数,是每个金蛋内的数字 -32768 ≤ a[i] ≤ 32767。

输出格式

输出 第一行有一个整数,表示起始位置编号。 第二行有一个整数,表示终止位置编号。 第三行有一个数,是奖励的和。 注:若有多个解,只输出起始位置编号最小的解,若多个解终止位置编号相同,则输出最小的编号。

样例

输入:

5
-2 2 5 -1 6

输出:

2
5
12

数据范围与提示

对于30%的数据,n<=100 对于60%的数据,n<=400 对于100%的数据,n<=1,000,000