问题重述

比尔正在开发一种新的数学理论来研究人类情感。他的最新研究致力于探讨好日子或坏日子如何影响人们对某段生活的记忆。

比尔为人类生活的每一天分配了一个非负整数值，称为“情感值”。情感值越大，表示这一天越好。比尔认为，某段生活的价值与该段时间内所有日子的情感值之和乘以该段时间内最小的情感值成正比。这个模型反映了即使平均来说不错的时期也可能因为某一天非常糟糕而被大大破坏。

现在，比尔计划研究自己的生活，并找出他生活中价值最高的那段时期。我们需要帮助他完成这个任务。

输入格式

• 第一行是一个整数 $n$，表示比尔计划研究的生活天数（$1 \leq n \leq 100,000$）。
• 接下来的 $n$ 个整数 $a_1, a_2, \ldots, a_n$（每个 $a_i$ 的范围是 $0$ 到 $10^6$），表示每天的情感值。数字之间用空格和/或换行分隔。

输出格式

• 第一行输出某段生活的最大价值。
• 第二行输出两个整数 $l$ 和 $r$，表示从第 $l$ 天到第 $r$ 天（包括 $l$ 和 $r$）的这段生活的价值是最大的。如果有多个这样的时期，输出任意一个即可。

示例输入 1

6
3 1 6 4 5 2

示例输出 1

60
3 5

来源

Northeastern Europe 2005