Largest Rectangle in Histogram

Given a histogram where each bar has a width of 1 and a non-negative height, your task is to determine the area of the largest rectangle that can be formed within the bounds of the histogram. The area of a rectangle formed by consecutive bars is computed as

$$ \text{area} = \text{height} \times \text{width} $$

where \(\text{height}\) is the minimum height among the selected bars and \(\text{width}\) is the number of bars used.

You will be given an integer \(n\) representing the number of bars, followed by \(n\) space-separated integers indicating the height of each bar. Print the maximum rectangular area that can be formed.

inputFormat

The first line contains a single integer \(n\) (the number of bars in the histogram). The second line contains \(n\) space-separated non-negative integers representing the heights of the histogram bars.

For example:

7
2 1 5 6 2 3 1

outputFormat

Output a single integer, the maximum rectangular area that can be formed in the histogram.

1
5

5