Largest Rectangle in a Histogram

Given a histogram with n contiguous bars (each of unit width), your task is to determine the area of the largest rectangle that can be formed using one or more consecutive bars.

The area of a rectangle formed by a sequence of bars is given by the formula: $Area = h \times w$, where $h$ is the minimum height among the selected bars and $w$ is the number of bars selected.

For example, for the histogram [2, 1, 5, 6, 2, 3], the largest rectangle has an area of 10.

inputFormat

The input is given via standard input (stdin). The first line contains an integer n indicating the number of bars in the histogram. If n > 0, the second line contains n space-separated non-negative integers representing the heights of the histogram bars. If n is 0, the histogram is empty.

outputFormat

Output a single integer to standard output (stdout) which is the area of the largest rectangle that can be formed within the histogram.

6
2 1 5 6 2 3

10