Largest Rectangle in Histogram

Given a histogram represented by a sequence of non-negative integers, where each integer represents the height of a building of unit width, your task is to find the area of the largest rectangle that can be formed within the bounds of the histogram.

The rectangle must be formed by consecutive buildings, and its area is determined by the height of the shortest building in the selected range multiplied by the number of buildings in that range.

This is a classic problem in algorithm design and can be solved efficiently using a stack-based strategy.

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

inputFormat

The first line contains an integer \( n \) (\(0 \le n \le 10^5\)) representing the number of buildings. The second line contains \( n \) space-separated non-negative integers representing the heights of the buildings.

If \( n = 0 \), there will be no second line and the result should be 0.

outputFormat

Output a single integer representing the maximum rectangular area that can be obtained.

6
2 1 5 6 2 3

10