Choosing a Subarray 2

You are given a one-dimensional array A[1], ..., A[N] of length N (1 <= N <= 100,000).

Choose two integers i and j such that 1 <= i <= j <= N, forming the subarray A[i], ..., A[j]. The score of this subarray is defined as follows.

(A[i] + ... + A[j]) * min{A[i], ..., A[j]}

In other words, the score is the sum of the subarray multiplied by the minimum value inside that subarray.

Given A, write a program that finds the maximum possible score and prints an interval that achieves it.

The first line contains the integer N.

The second line contains N integers representing A[1], ..., A[N]. Each integer is between 0 and 1,000,000, inclusive.

Print the maximum possible score on the first line.

On the second line, print the start position i and end position j of an interval that achieves that score.