Maximum Rectangle Area in a Histogram

Given a histogram with \( n \) bars, each having a width of 1, your task is to compute the maximum rectangular area that can be formed by consecutive bars. The rectangle's area is defined as the number of bars multiplied by the minimum height among those bars. Formally, for an array of non-negative integers \( H[0 \ldots n-1] \), you need to compute

[ \max_{0\le i \le j < n} { (j - i + 1) \times (\min_{k=i}^{j} H[k]) } ]

For example, consider the histogram given by [2, 1, 5, 6, 2, 3]. The largest rectangular area is 10.

inputFormat

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

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

outputFormat

Output a single integer on standard output (stdout), which is the maximum rectangular area that can be obtained in the given histogram.

6
2 1 5 6 2 3

10