Largest Rectangle in a Histogram

Given an array of building heights, your task is to determine the maximum possible rectangular area that can be formed by choosing a contiguous subarray of these buildings. The area of a rectangle is calculated as \(\text{area} = \text{height} \times \text{width}\), where \(\text{width}\) is the number of consecutive buildings selected and \(\text{height}\) is the minimum height among these buildings. This problem is a classic application of the stack data structure and requires careful handling of indices to compute areas efficiently.

inputFormat

The input is read from stdin and consists of multiple test cases. The first line contains a single integer \(T\) indicating the number of test cases. Each test case starts with an integer \(n\), the number of buildings, followed by a line containing \(n\) space-separated positive integers representing the heights of the buildings.

outputFormat

For each test case, output a single line displaying the maximum rectangular area that can be formed in the histogram. The output should be written to stdout.

2
6
2 1 5 6 2 3
4
1 2 3 4

10
6