Largest Rectangle in Histogram

Given a histogram where the width of each bar is 1 and the height of each bar is given by an integer array, find the largest rectangular area that can be formed in the histogram. The rectangle must be contiguous and its area is computed as:

$$A = h \times w,$$

where \(h\) is the height of the rectangle and \(w\) is the width (i.e. the number of consecutive bars included). This problem requires you to determine the maximum area possible using one or more adjacent bars.

Note: If the histogram is empty (i.e. no bars), the area is 0.

inputFormat

The input is given via stdin and has two lines:

• The first line contains a non-negative integer n, 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 zero, the second line will be empty.

outputFormat

Output the maximum rectangular area that can be formed within the histogram. The output should be written to stdout and must be followed by a newline character.

## sample

6
2 1 5 6 2 3

10

</p>