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?


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 )


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



Special for my good friend wqb0039 !