Description

After windy did fgjlwj's game.windy feel so dull. So wqb0039 wanted to pick a most delicious rectangle to windy from the cake with the size of 1*n. Each grid has a score of delicious which is a positive integers. And the delicious score of the rectangle which from the ith grid to jth grid, is the lowest score grid of the rectangle's score times the sum of all scores of the rectangle. Which is the most delicious rectangle?

Input

Multiple test cases. Each contains two lines. The first line contains one integers n. The second line contains n positive integers which is not bigger than 10^6. ( 1 <= k <= n <= 10^5 )

Output

For each test case,output only one line,the most delicious rectangle's score.

Sample Input

6 3 1 6 4 5 2

Sample Output

60

Author

windy7926778
Special for my good friend wqb0039 !