Largest Rectangle in Histogram

You are given a histogram where each bar has a width of 1 and varying heights. Your task is to find the largest rectangular area that can be formed within the bounds of contiguous bars.

Formally, given an array of integers \( h[0 \dots n-1] \), the area of a rectangle spanning indices \( i \) to \( j \) is defined as:

\( \text{Area} = \min\{h[i], h[i+1], \dots, h[j]\} \times (j - i + 1) \)

Your goal is to compute the maximum such area using an efficient algorithm.

inputFormat

Input is given via standard input. The first line contains an integer n, representing the number of bars in the histogram. The second line contains n space-separated positive integers, where each integer represents the height of a bar.

outputFormat

Output a single integer, which is the maximum area of a rectangle that can be formed in the histogram.## sample

7
2 1 5 6 2 3 1

10