Description
There are N bars line up in a row. The height of the i-th bar is hi, and the width of each bar is 1. Please find the largest rectangle in it.
Sample test:
Input
The first line has an integer T, means there are T testcases.
The first line of each testcase contains an integer N, and the second line contains N integers h1 ~ hN.
1 <= hi <= 1e9.
1 <= T <= 10.
In testcase 1 ~ 4: 1 <= N <= 1000.
In testcase 5 ~ 8: 1 <= N <= 2e5.
Output
Please print the area of the largest rectangle for each testcase.