A Scary Part-Time Job

Interview

Time limit1sMemory limit512 MB

Summary

Given daily wages, choose a contiguous range maximizing (length of range) times (minimum wage in that range).

Level: Medium6 of 10
Topics: Stack, Greedy
Solved: No attempts yet

Problem

Seonghwa owns a convenience store and pays wages in an unusual way.

The amount of work changes from day to day, so the daily wage for each day is fixed in advance.
Nobody is paid on the day worked. The whole sum is handed over when the worker quits.
Seonghwa is greedy, so he settles up using the lowest daily wage inside the period worked. The payout is (number of days worked) times (the lowest daily wage in that period).
To hide the fact that the daily wage changes, he never rehires anyone who has quit. Once you take the job you must show up every single day from your first day to your last.

Junsu needs to pay rent, so he wants to work at this store. A former employee explained the pay rule to him, and he has also learned the daily wage for each of the next $n$ days. Junsu picks one contiguous range of days between day 1 and day $n$ and works exactly that range. Working longer does not always pay more.

Find the largest payout Junsu can get.

Input

The first line contains the number of days available for work, $n$ ( $0 < n \le 100000$ ).

The second line contains the daily wages $T_i$ for day 1 through day $n$ , in order ( $0 < T_i \le 1000000$ ).

Output

Print the largest payout Junsu can get on one line.

Examples6

Example 1
Input
```
5
10 20 30 20 10
```
Expected output
```
60
```
Example 2
Input
```
1
1000000
```
Expected output
```
1000000
```
Example 3
Input
```
1
1
```
Expected output
```
1
```
Example 4
Input
```
6
1 2 3 4 5 6
```
Expected output
```
12
```
Example 5
Input
```
6
6 5 4 3 2 1
```
Expected output
```
12
```
Example 6
Input
```
7
5 1 5 5 1 5 5
```
Expected output
```
10
```