题目描述

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为 2,1,4,5,1,3,3 的矩形组成的直方图，矩形的宽度都为 1 ：

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

输入格式

有多组测试数据，每组数据占一行。输入零时读入结束。

每行开头为一个数字 $n(1\le n\le 10^5)$，接下来在同一行给出 $n$ 个数字 $h_1,h_2,\cdots, h_n (0\le hi\le 10^9)$，表示每个矩形的高度。

输出格式

对于每组数据，输出最大子矩阵面积，一组数据输出一行。

输入输出样例 #1

输入 #1

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

输出 #1

8
4000