该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

正如标题所说，这是一道典题

直方图是由一系列沿共同基线对齐的矩形组成的多边形。这些矩形宽度相同但高度可能不同。例如，左图展示了一个由高度分别为2、1、4、5、1、3、3（单位宽度为1）的矩形构成的直方图：

通常直方图用于表示离散分布，例如文本中字符的出现频率。需要注意的是矩形的排列顺序（即它们的高度）非常重要。

设直方图有$n$根宽度均为 1 的矩形条，其高度依次为$h_1, h_2, \dots, h_n.$

对于任意连续区间 $[i, j]，1 \le i \le j \le n$，其能覆盖的矩形面积为：
$A(i, j) \;=\; (j - i + 1)\;\times\;\min_{\,k = i,\dots,j} h_k.$

则与基线对齐的最大矩形面积定义为：
$A_{\max} \;=\; \max_{1 \le i \le j \le n} \bigl[(j - i + 1)\,\min_{k = i}^{j} h_k \bigr].$

右图便展示了该直方图对应的最大对齐矩形。

请计算直方图中与基线对齐的最大矩形面积。

输入格式

第一行为一个整数$T(1 \le T \le 10)$，测试用例的数量。

接下来$T$行，每个测试用例描述一个直方图：

首先给出整数$n(1 \le n \le 10^5)$表示组成该直方图的矩形数量。

随后是$n$个整数$h_1, h_2,...,h_n(1 \le h_i \le 10^9)$，按从左到右的顺序表示各矩形的高度。每个矩形的宽度为$1$。

输出格式

对于每组测试用例，输出一行一个整数，表示指定直方图中与基线对齐的最大矩形面积。

样例

2
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000

8
4000