Largest Rectangle in a Histogram

This problem asks you to compute the largest rectangular area in a histogram. You are given several test cases. In each test case, the histogram is represented by N bars where each bar has a width of 1 and a given height. A rectangle in the histogram is formed by a contiguous sequence of bars, and its area is the product of the minimum height in that range and the number of bars considered.

Your task is to determine the maximum rectangle area that can be formed from consecutive bars in each histogram.

Hint: An efficient solution uses a stack to track the indices of the bars, which helps in calculating the area in O(N) time for each histogram.

inputFormat

The input will be read from standard input (stdin). The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer N representing the number of bars in the histogram. The next line contains N space-separated integers where each integer represents the height of a bar.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum rectangular area that can be formed in the corresponding histogram.## sample

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

5
9
9
12
15