Largest Rectangle in a Histogram

In this problem, you are given a histogram represented as a sequence of bars, where each bar's height is provided. Your task is to compute the area of the largest rectangle that can be formed within the bounds of the histogram.

More formally, given an integer $n$ and an array of $n$ integers (h_1, h_2, \ldots, h_n), you need to find the maximum value of (A = h_i \times (j - i + 1)) such that the rectangle defined from index (i) to index (j) (inclusive) has a height no smaller than the smallest height among (h_i, ..., h_j).

inputFormat

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

outputFormat

Output a single integer representing the area of the largest rectangle that can be formed in the histogram.## sample

7
6 2 5 4 5 1 6

12