Maximum Rectangle Area in a Histogram

You are given a histogram represented by a sequence of non-negative integers. Each integer corresponds to the height of a building with a width of 1 unit. Your task is to determine the maximum rectangular area that can be formed within this histogram.

The area of a rectangle is defined as:

\(\text{Area} = \text{height} \times \text{width}\)

This problem requires efficiently computing the largest rectangle that can be formed by using contiguous buildings in the histogram.

inputFormat

The input is read from stdin. The first line contains an integer n (n ≥ 0) representing the number of buildings in the histogram. The next line contains n space-separated integers which denote the heights of the buildings.

outputFormat

Output a single integer to stdout representing the maximum rectangular area that can be formed using contiguous buildings in the histogram.## sample

6
2 1 5 6 2 3

10