Maximum Rectangle Area in Histogram

You are given a histogram where each bar has a unit width and a specified height. Your task is to calculate the maximum rectangular area that can be formed within the bounds of the histogram. In other words, you need to find the largest area rectangle that can be completely contained in the histogram.

The area of a rectangle formed by consecutive bars can be computed using the formula: \( \text{area} = \text{min(height)} \times \text{width} \).

This problem is fundamental in array processing and optimization, and an efficient solution is required to handle large histograms.

inputFormat

The first line of input contains an integer \( T \) representing the number of test cases. Each test case is described in two lines. The first line contains an integer \( n \) denoting the number of bars in the histogram. The second line contains \( n \) space-separated integers, where each integer represents the height of a bar in the histogram.

outputFormat

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

Each result should be printed on a new line.

## sample

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

10
12
9
5
15

</p>