1630 - largest rectangle

Time Limit: 1s Memory Limit: 128MB

Submissions: 214 Solved: 102
Description
Given n positive 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.
Input
  The first line of the input file contains an integer T (T<=100) specifying the number of test cases.
Each test case begins with a line containing an integer N (1<=N<=100000),The following N-1 lines each contain a integer A[i](1<=A[i]<=10000).
Output
 For each query, output a single line containing largest area. 
Sample Input
2
6
2
1
5
6
2
3
10
1
2
3
4
5
6
7
9
10
8
Sample Output
10
30
Hint
Source
The 8th(2013) ACM Programming Contest of HUST