Largest Rectangle in Histogram

You are given one or more histograms, each representing the skyline of buildings. For each histogram, you are required to compute the maximum area of a rectangle that can be formed using contiguous buildings. The building heights of a histogram are given as an array of positive integers, and the rectangle's area is determined by multiplying the number of contiguous buildings (its width) by the minimum height among them.

This problem can be formalized as follows:

Given a histogram with bars of heights \(h_1, h_2, \dots, h_n\), find the maximum area defined by \[ \max_{1 \le i \le j \le n} \{ (j - i + 1) \times \min_{i \le k \le j} h_k \}. \]

An efficient solution is achievable using a stack-based algorithm with a time complexity of \(O(n)\). Read the input from standard input and print the output to standard output, with one answer per line for each test case.

inputFormat

The first line contains an integer \(t\) representing the number of test cases. Each test case is described in two lines. The first line of a test case contains an integer \(n\), the number of buildings. The second line contains \(n\) space-separated integers, representing the heights of the buildings.

outputFormat

For each test case, output a single line containing the maximum rectangular area that can be formed within the histogram.

## sample

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

10
4

</p>