Largest Rectangle in Histogram

Given a histogram where the width of each bar is 1, your task is to find the area of the largest rectangle that can be formed within the bounds of the histogram. The rectangle must be formed by consecutive bars.

You are given an integer n representing the number of bars, followed by n integers that denote the heights of the bars. The area of a rectangle formed by consecutive bars is computed by

\( A = h \times w \)

where \( h \) is the height of the rectangle (determined by the minimum bar height in the selected range) and \( w \) is the number of bars in the rectangle.

Your task is to output a single integer denoting the maximum area of any such rectangle.

inputFormat

The first line contains an integer n ( 0 \(\leq\) n \(\leq\) 10⁵), which is the number of bars. The second line contains n space-separated non-negative integers representing the heights of the bars.

If n is 0, the histogram is empty.

outputFormat

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

6
2 1 5 6 2 3

10