Largest Rectangle in Histogram

Given an array representing the heights of consecutive buildings in a histogram, your task is to calculate the area of the largest rectangle that can be formed within the confines of the histogram. The rectangle must be formed by adjacent buildings. More formally, if the input array is heights of size n, find the maximum area such that for some indices i and j (with 0 ≤ i ≤ j < n), the area is computed as:

$$Area = (j - i + 1) \times \min\{heights[i], heights[i+1], \ldots, heights[j]\}. $$

This problem is a classic application of stack data structures and has an optimal solution with time complexity \(O(n)\). It is widely used to test one’s ability to use monotonic stacks in algorithm design.

inputFormat

The first line of the input contains a single integer n representing the number of bars in the histogram. The second line contains n space-separated integers, where each integer represents the height of a building in the histogram.

You should read from standard input (stdin).

outputFormat

Output a single integer that represents the area of the largest rectangle that can be formed in the histogram. The result should be written to standard output (stdout).

## sample

6
2 1 5 6 2 3

10