Largest Rectangle in a Skyline Histogram

Given a histogram where the width of each bar is 1, your task is to calculate the largest rectangular area that can be formed in the histogram. For each test case, you are given an integer N representing the number of bars followed by N space-separated integers that denote the height of each bar. You need to compute the maximum area of a rectangle that can be formed by contiguous bars.

The area of a rectangle is defined as:

$$area = height \times width$$

where height is the minimum height among the bars in the chosen segment and width is the number of bars in that segment.

This problem combines the use of stacks and efficient processing of range queries. It is a classic algorithmic challenge often referred to as the "Largest Rectangle in Histogram" problem.

inputFormat

The first line of the input contains an integer T denoting the number of test cases. Each test case consists of two lines: the first line contains an integer N representing the number of bars in the histogram, and the second line contains N space-separated integers representing the heights of the histogram bars.

outputFormat

For each test case, output a single line containing the maximum rectangular area that can be formed in the given histogram.## sample

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

10
6