Time Limit: 1s
Memory Limit: 256MB
Given N non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Given height = [2,1,5,6,2,3],
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N, followed by integers height,...,height[N] on the second line.
1 <= T <= 100
1 <= N <= 100000
1 <= height[i] <= 1000
Output T lines, one for each test case, containing the largest rectangle area.