Largest Rectangle in Histogram

You are given a histogram which is represented by an array of non-negative integers. Each integer in the array represents the height of a histogram bar. All bars have a unit width. Your task is to compute the area of the largest rectangle that can be formed within the bounds of the histogram.

For a given histogram H with bars H[i] for i = 0, 1, ..., n-1, a rectangle is formed by a contiguous segment of bars. If the rectangle spans bars i to j, then the area of this rectangle is given by:

\(\text{Area} = \min\{H[i], H[i+1], \ldots, H[j]\} \times (j-i+1)\)

Your goal is to find the maximum possible area of such a rectangle.

inputFormat

The input is given in stdin and consists of two lines:

• The first line contains a single integer n (\(n \ge 0\)), the number of bars in the histogram.
• The second line contains n space-separated integers representing the heights of the histogram bars. If n is 0, the second line may be empty.

outputFormat

Output a single integer to stdout, which is the area of the largest rectangle that can be formed within the histogram.

6
2 1 5 6 2 3

10