Largest Rectangle in Histogram

Given a histogram represented by an array of bar heights, your task is to compute the area of the largest rectangle that can be formed within the histogram.

More formally, let the histogram be represented by an array \(\textbf{heights}\), where each \(\textbf{heights}[i]\) is the height of the \(i\)-th bar. A rectangle is defined by a contiguous sequence of bars, and its area is given by \(h \times w\), where \(h\) is the minimum height among the selected bars and \(w\) is the number of bars chosen. Expressed in \(\LaTeX\), for indices \(i\) to \(j\), the rectangle area is \[ \text{Area} = \min_{i \le k \le j} \textbf{heights}[k] \times (j - i + 1)\,. \] Your goal is to determine the maximum such area.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing the number of bars in the histogram. The second line contains (n) space-separated positive integers representing the heights of the histogram bars.

outputFormat

Output to standard output (stdout) a single integer representing the area of the largest rectangle that can be formed in the histogram.## sample

6
2 1 5 6 2 3

10