Largest Rectangle in a Skyline

You are given a skyline represented as a sequence of building heights. Your task is to compute the largest rectangle (by area) that can be formed within the skyline. The rectangle must be formed by consecutive buildings and its area is determined by the minimum height among these buildings multiplied by the number of buildings.

More formally, for a given sequence of heights \(h_1, h_2, \ldots, h_n\), you need to determine: \[ \text{Area} = \max_{1 \leq i \leq j \leq n} \{(j - i + 1) \times \min_{i \leq k \leq j} (h_k)\} \]

You will be given multiple test cases. For each test case, output the maximum rectangle area that can be formed.

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. For each test case:

• The first line contains an integer \(n\) which is the number of buildings.
• The second line contains \(n\) space-separated integers representing the heights of the buildings.

It is guaranteed that \(n \geq 1\).

outputFormat

For each test case, output a single integer in a new line representing the maximum rectangular area that can be formed within the skyline.

## sample

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

10
12
10

</p>