Largest Rectangle in Histogram

The task is to compute the largest rectangular area in a histogram. You are given a sequence of integers where each integer represents the height of a histogram bar. The goal is to find a contiguous segment of bars such that the rectangle, formed by the height of the shortest bar in the segment and the width equal to the number of bars in the segment, has the maximum possible area.

The area of a rectangle is given by: $$area = height \times width$$, where \(height\) is the minimum height among the selected consecutive bars and \(width\) is the number of bars in that segment.

You need to process multiple test cases. For each test case, the first number gives the number of bars \(n\), followed by \(n\) integers representing the histogram heights.

inputFormat

The input begins with an integer \(t\) representing the number of test cases. Each test case consists of two lines:

1. The first line contains an integer \(n\), the number of bars in the histogram.
2. The second line contains \(n\) space-separated integers representing the heights of the bars.

outputFormat

For each test case, output a single integer which is the maximum rectangular area found in the histogram. Each answer should be printed on a new line.

## sample

1
7
2 1 5 6 2 3 2

10

</p>