StackMonotonic StackArray
A histogram has bars of width 1 with the given heights. Find the area of the largest rectangle that fits entirely inside the histogram.
Input
Line 1: n. Line 2: n bar heights.
Output
Print the largest rectangle area.
Constraints
1 <= n <= 10^5 0 <= height <= 10^4
Example 1
Input
6 2 1 5 6 2 3
Output
10
The bars of height 5 and 6 form a rectangle of height 5 and width 2, area 10.