题目描述

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

输入格式

输入格式 第一行输入一个正整数； 第二行有 $n$ 个整数，是每个金蛋内的数字 $-32768 \le a_i \le 32767$ 。

输出格式

输出第一行有一个整数，表示起始位置编号。 第二行有一个整数，表示终止位置编号。 第三行有一个数，是奖励的和。

注：若有多个解，只输出起始位置编号最小的解，若多个解终止位置编号相同，则输出最小的编号。

样例

5
-2 2 5 -1 6

2
5
12

数据规模与约定

对于 $30 \%$ 的数据, $n \le 100$

对于 $60 \%$ 的数据, $n \le 400$

对于 $100 \%$ 的数据, $n \le 1000000$