题目描述

比尔正在为人类情感开发一种新的数学理论。他最近的调查致力于研究好日子或坏日子如何影响人们对某些生活时期的记忆。
比尔最近提出的一个新想法是为人类生活的每一天分配一个非负整数值。
比尔将这一价值称为当天的情感价值。情感价值越大，日子就越好。比尔建议，人类生命的某个时期的价值与给定时期内各天的情感价值之和乘以其中一天的最小情感价值成正比。这个模式反映了一个非常糟糕的日子可能会大大破坏平均时期的好时光。
现在比尔正计划调查自己的生活，找出他生命中最有价值的时期。帮助他这样做。

输入格式

输入的第一行包含一个整数 n 表示生命中的天数 (1 <= n <= 100 000)。
记下来 n 个整数 a1, a2, ... 范围从 0 到 10^6，表示这些天的情绪值。数字由空格分隔。

输出格式

在第一行打印比尔生命中某个时期的最大价值。在第二行打印两个数字 l 和 r，使得比尔生命中第 l 天到第 r 天（含）的这段时间具有最大可能的值。如果有多个具有最大可能值的时期，则打印其中任何一个。

样例数据

input

6 
3 1 6 4 5 2

output

60 
3 5