Choosing a Subarray

There is a one-dimensional array A[1], ..., A[N] of size N (1 <= N <= 100,000).

For indices i and j with 1 <= i <= j <= N, the score of the subarray from i to j is

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

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

Given the array, find the maximum possible score among all contiguous subarrays.

The first line contains the integer N.

The second line contains the integers A[1], ..., A[N]. Each integer is nonnegative and does not exceed 1,000,000.

Print the maximum score on the first line.

If i = 3 and j = 5, the score is (6 + 4 + 5) * 4 = 60.