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

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