Histogram - MarisaOJ: Marisa Online Judge

Histogram

Time limit: 1000 ms
Memory limit: 256 MB
Find the biggest rectangle that can be formed in a given histogram using a series of adjacent bars with heights specified in an array. Assume all bars have the same width of 1 unit for simplicity. Visual representation for the sample test: ![](/media/media/ViYehcOKmRQ3v2M5eo200g.png) ### Input - The first line contains an integer $n$, the number of bars in the histogram. - The second line contains $n$ integers $h_i$, the bars height in the histogram, from left to right. ### Output - Print the maximum rectangle area. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i \le 10^9$. ### Example Input: ``` 6 2 1 5 6 2 3 ``` Output: ``` 10 ```