Maximum Rectangle Area in Histogram

You are given several histograms, each represented by a sequence of non-negative integers corresponding to the heights of bars. Your task is to compute the maximum rectangular area that can be formed within the histogram for each test case.

For a histogram with n bars, where the height of the i-th bar is h_i, the area of a rectangle composed of consecutive bars is calculated as:

\(area = h \times w\)

where h is the minimum height among the selected bars and w is the number of bars selected.

Apply an efficient algorithm (e.g. a stack based solution) to compute the maximum possible area for each histogram.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains a single integer t, the number of test cases.
• For each test case, the first line contains a single integer n representing the number of bars in the histogram.
• The next line contains n space-separated integers representing the heights of the histogram bars.

It is guaranteed that each test case contains exactly n non-negative integers.

outputFormat

For each test case, print a single line to standard output (stdout) containing one integer: the maximum rectangular area that can be formed within the histogram.

## sample

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

10
16
12

</p>