A histogram has n bars, numbered left to right, each of width 1 and a given non-negative integer height. Consider every rectangle that (a) has its base on the x-axis, (b) spans some contiguous range of bars, and (c) is exactly as tall as the shortest bar in that range (so it fits entirely under the skyline formed by the bars). Find the maximum possible area of such a rectangle.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the bar heights left to right.
Output format
A single integer: the maximum rectangle area.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ height ≤ 1000000000