spaceship

The vogon spaceships have a peculiar velocity-control: a large number of buttons in a row, each of which is labelled with a positive integer: s1,...,sN. The mode of operation is the following: the vogon pilot clears the current setting (it means that all the buttons gets into the state OFF), then he chooses a continous sequence of buttons: si,si+1,...,sj, (i≤j), then he pushes all of these buttons to ON state. Finally he pushes the main-button. The result of this (sometimes very long) procedure that the ship accelerates/decelerates to the velocity given by the formula:

(j-i+1)*min({si,...,sj}) Your task is to compute the maximal possible velocity of the ship (M).

Example

    N: 4
    The numbers on the buttons are: 4,1,2,3
    By exploring every possible choice, we see that the maximal velocity is 4:

        i,j    v
        --------
        1,1 -> 4
        1,2 -> 2
        1,3 -> 3
        1,4 -> 4
        2,2 -> 1
        2,3 -> 2
        2,4 -> 3
        3,3 -> 2
        3,4 -> 4
        4,4 -> 3

Input Specification

 
N
s1 ... sN

The first line is the number 1 ≤ N ≤ 105 of the buttons the ship has. The space seaparated numbers 1 ≤ sk ≤ 109 (k=1...N) come in the second line.

Output Specification

M

A line with the maximal velocity M.

Sample Input 1

1. 4
2. 4 1 2 3

download as text file

Sample Output 1

1. 4

download as text file

Sample Input 2

1. 4
2. 3 2 2 1

download as text file

Sample Output 2

1. 6

download as text file