Largest Rectangle in Histogram

Given a histogram where each bar is of unit width and the i-th bar has a non-negative integer height, find the area of the largest rectangle that can be formed by one or more contiguous bars. The area of a rectangle formed by contiguous bars is computed as \(\text{area} = \text{height} \times \text{width}\), where the height is the minimum bar height in that contiguous segment and the width is the number of bars in the segment.

Your task is to design an algorithm that computes the maximum rectangular area in the histogram.

inputFormat

The first line contains an integer \(n\) representing the number of bars in the histogram. The second line contains \(n\) space-separated integers, each denoting the height of a bar.

outputFormat

Output a single integer representing the area of the largest rectangle in the histogram.

6
2 1 5 6 2 3

10