Largest Rectangle in Histogram

Given a histogram where each bar has a unit width and a non-negative height, compute the area of the largest rectangle that can be formed within the bounds of the histogram.

The histogram is represented by an array of integers, where each integer denotes the height of a bar. The problem is to determine the maximum area of a rectangle formed by contiguous bars.

Mathematically, if the histogram is represented as \( \textbf{heights} = [h_1, h_2, \dots, h_n] \), then you are required to find the maximum value of \( \max_{1 \leq i \leq j \leq n} \left\{ \min_{i \leq k \leq j} h_k \times (j - i + 1) \right\} \).

inputFormat

The input is read from standard input (stdin) and consists of two lines.

The first line contains an integer \( n \) representing the number of bars in the histogram.

The second line contains \( n \) non-negative integers separated by spaces, which represent the heights of the histogram bars.

outputFormat

Output a single integer representing the maximum rectangular area that can be formed in the histogram. The output is written to standard output (stdout).

6
2 1 5 6 2 3

10