Largest Rectangle in Histogram

Given an array of non-negative integers representing the heights of bars in a histogram, your task is to compute the area of the largest rectangle that can be formed within the histogram.

For a rectangle with height h and width w, the area is given by the formula: \(\text{Area} = h \times w\). Use an efficient algorithm to handle large inputs.

inputFormat

The input is provided via standard input. The format is as follows:

• The first line contains an 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 bar.

outputFormat

Output to standard output a single integer which is the area of the largest rectangle that can be formed within the histogram.

6
2 1 5 6 2 3

10