Largest Rectangle in a Histogram

Given a histogram consisting of bars where each bar has a unit width and a specified height, your task is to calculate the area of the largest rectangle that can be formed within the bounds of the histogram.

The rectangle must be formed by consecutive bars and its height is determined by the minimum height among those bars. Mathematically, if we denote the heights as \(h_1, h_2, \dots, h_n\), then the area of a rectangle covering indices from \(i\) to \(j\) is

\(A = \min\{h_i, h_{i+1}, \dots, h_j\} \times (j - i + 1)\)

Your goal is to find the maximum such area.

inputFormat

The first line contains an integer \(n\) denoting the number of histogram bars. The second line contains \(n\) space-separated integers representing the heights of the histogram bars.

outputFormat

Output a single integer which is the largest rectangular area in the given histogram.

6
2 1 5 6 2 3

10