题目描述

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

通常，直方图用于表示离散分布，例如文本中字符的频率。需要注意的是，矩形的顺序（即它们的高度）非常重要。请计算直方图中与基线对齐的最大矩形的面积。右图展示了给定直方图中最大的对齐矩形。

输入格式

输入包含多个测试用例。每个测试用例描述一个直方图，并以一个整数 $n$ 开头，表示组成直方图的矩形数量。你可以假设 $1 \leq n \leq 100000$。接下来是 $n$ 个整数 $h_1, \dots, h_n$，其中 $0 \leq h_i \leq 1000000000$。这些数字按从左到右的顺序表示直方图中矩形的高度。每个矩形的宽度为 $1$。最后一个测试用例的输入后跟一个 $0$。

输出格式

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

示例输入

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

示例输出

8
4000

提示

输入数据量较大，建议使用 scanf 读取输入。

题目来源

乌尔姆 $2003$ 年本地竞赛