Maximum Rectangular Area in a Histogram

Given a histogram represented by a list of building heights, your task is to calculate the maximum rectangular area that can be formed within the histogram. The rectangle must be formed by consecutive buildings. The area is determined by the shortest building within that range multiplied by the number of buildings in the range.

More formally, for a histogram with heights \(h_1, h_2, \dots, h_n\), you need to find the maximum value of \(A = (\min_{i \leq j \leq k} h_j) \times (k-i+1)\) over all intervals \([i,k]\).

The input is given through standard input and the output should be printed to standard output.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(n\) indicating the number of buildings. The next line contains \(n\) space-separated integers representing the heights of the histogram bars.

Example:

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

outputFormat

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

Example Output:

10
25
5
9
9
12

## sample

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

10
25
5
9
9
12

</p>