Largest Rectangular Area in a Histogram
Given
n numbers representing the heights of bars in a histogram, you are asked to calculate the largest area that can be obtained in the histogram without going out of the bars.All the bars in the histogram have a width of 1, while the heights are arbitrary nonnegative integers.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next line contains
n space-separated integers (0 ≤ ≤ ).Output
The program should print the largest area possible to obtain from the bars of the histogram.
Examples
Input | Output |
8
6 2 5 4 5 1 6 1 | 12 |
Hint
For each element in the histogram, you can calculate 2 numbers - the closest element that’s smaller than the current element on the left and on the right. That would be sufficient to calculate the area of the rectangle having the height of the current bar.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB