Largest Rectangle in Histogram

You are given a histogram consisting of N bars, where the width of each bar is 1 and the heights of the bars are provided in an array. Your task is to compute the area of the largest rectangle that can be formed within the histogram.

For any contiguous set of bars, the area of the rectangle is given by:

\(A = h \times w\)

where \(h\) is the minimum height among the chosen bars and \(w\) is the number of bars in the selection. In other words, if you choose bars in the range \([i, j]\), the area is:

\(A = \min_{i \le k \le j} \{ h[k] \} \times (j - i + 1)\)

Your solution should process multiple test cases.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each test case consists of two lines. The first line of a test case contains an integer (N) indicating the number of bars in the histogram. The second line contains (N) space-separated integers representing the heights of the bars.

outputFormat

For each test case, output a single line on standard output (stdout) representing the maximum rectangular area that can be formed within the histogram.## sample

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

12
12
9
20
6