Largest Rectangle in a Histogram

Given an array of building heights representing a histogram, your task is to determine the largest rectangular area that can be formed using contiguous buildings. The area is computed as the height of the smallest building in a contiguous segment multiplied by the number of buildings in that segment. In mathematical terms, for a given width \( w \) and minimum height \( h \) in that segment, the area is given by \( \text{area} = h \times w \).

For example, consider the histogram with heights [2, 1, 5, 6, 2, 3]. The largest rectangle has an area of 10.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \( n \) (1 \( \le n \le 10^5 \)), representing the number of buildings in the histogram. The second line contains \( n \) space-separated integers which represent the heights of the buildings.

outputFormat

Output a single integer to standard output (stdout), which is the maximum area of a rectangle that can be formed in the histogram.

6
2 1 5 6 2 3

10