Time Limit: 1s
Memory Limit: 256MB

Submissions: 81 Solved: 25

- Description
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.

For example,

Given height = [2,1,5,6,2,3],

return 10.

- Input
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N, followed by integers height[1],...,height[N] on the second line.

1 <= T <= 100

1 <= N <= 100000

1 <= height[i] <= 1000

- Output
Output T lines, one for each test case, containing the largest rectangle area.

- Sample Input
- Sample Output
- Hint
- Source