Largest Rectangle in a Histogram

Given a histogram where each bar has a unit width, your task is to find the area of the largest rectangle that can be formed using consecutive bars. Formally, if the histogram is represented by an array of positive integers \(h_1, h_2, \dots, h_n\), you need to compute the maximum area \(A\) where \(A = h \times k\) for some contiguous segment of \(k\) bars whose minimum height is \(h\).

For example, consider the histogram [2, 1, 5, 6, 2, 3, 5]. The largest rectangle has an area of 10.

inputFormat

The first line 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. 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 area of the largest rectangle that can be formed.

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

10
20
12