Largest Rectangle in Histogram

Given a histogram where the width of each bar is 1 and the heights of the bars are given by an array of integers, your task is to find the area of the largest rectangle that can be formed by contiguous bars.

The rectangle must be formed by selecting one or more consecutive bars. The area of the rectangle is the minimum height among the selected bars multiplied by the number of bars selected.

Formally, if the heights are given by \(h_1, h_2, \ldots, h_n\), then for any subarray \(h_i, h_{i+1}, \ldots, h_j\), the area is given by:

\(\text{Area} = \min_{i \leq k \leq j} h_k \times (j - i + 1)\).

Your program should read input from stdin and write the output to stdout.

inputFormat

The input consists of two lines:

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

outputFormat

Output a single integer which is the maximum rectangular area that can be formed by contiguous bars.

6
2 1 5 6 2 3

10