## 1644 - 第四届“恒生杯”程序设计大赛决赛 B

Time Limit : 1 Second

Memory Limit : 256 MB

Submission: 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