题目描述

小A从著名的齐鲁工带毕业后成为企鹅公司的一名会计员，怀揣着宏图理想的他，励志做成世界上最伟大的会计员，于是他每天都在加班处理数据表格，成功实现了“公司是我家”的成就。但经过一系列现实的毒打之后，他终究是进化成了摸鱼人。这天，老板逮到了正在摸鱼的小A，为了惩罚小A，给他布置了超额的任务。小A的摸鱼人属性绝不允许他再加一秒钟的班，为了正常下班，他不得不采用“不正常”的方法来完成任务。

“不正常”的方法是指：将数据表格内部的最大矩形面积作为这份表格的计算金额。其中数据表格是由多个宽度为 $1$ 高度不等的矩形构成

如下图：

（多个矩形组成的数据表格） （图中红色矩形为数据表格最大矩形）

（图中数字为每个矩形面积） （该红色矩形最大面积为2*8=16）

输入格式

第$1$行输入 $t$ , $t$ ( $1\\leq~t~\\leq~100$ ) 为测试组数

每组测试样例 第$1$行输入 $n$ ($1~\\leq~n~\\leq~10^4$), $n$ 指该数据表格为 $n$ 个矩形组成。

第 $2$ 行——第 $n + 1$ 行输入从左到右每个矩形的面积 $s$ ($1~\\leq~s~\\leq~10^9$)

输出格式

每行输出对应组的最大面积.

tips: cin,cout有可能超时，谨慎使用。

样例

2 
7 4 2 8 10 2 6 6 
6 
2 2 3 3 3 3 

16 
12