fence

Edoardo has a ranch in Pordenone, surrounded by tall mountains on three sides. Since his cows are always trying to escape, he built a fence on the fourth side, but soon realised that he does not need all of it. The fence consists of $N$ wooden poles, indexed from $0$ to $N-1$, and pole $i$ has a height of $H_i$ centimeters.

After removing some poles, the robustness of the remaining ones is the sum of $(j - i)\cdot min(H_i, H_j)$ over all $0 \le i < j < N$ such that poles $i$ and $j$ have not been removed and all those between them have been removed. Help Edoardo compute the maximum possible robustness over all possible choices of poles to remove.

Input data

The first line contains the integer $N$: the number of poles. The second line contains $N$ integers $H_i$: the height of the poles.

Output data

You need to write a single line with an integer: the maximum possible robustness over all possible choices of poles to remove.

Constraints and Clarifications

• $2 \le N \le 200 \ 000$.
• $0 \le H_i \le 1 \ 000 \ 000 \ 000$ for each $i=0\ldots N-1$.

Example 1

stdin

4
10 4 8 7

stdout

23

Explanation

In the first sample case, it is optimal to only remove pole $1$. The robustness of the remaining poles ($0,2,3$) is:
$(2-0)\cdot min(H_0, H_2) + (3-2) \cdot min(H_2,H_3) = 2 \cdot min(10, 8) + 1 \cdot min(8,7) = 23$.

Example 2

stdin

10
5 4 18 11 19 14 21 7 0 10

stdout

114