柱状图中的最大矩形 ## 来源 University of Ulm Local Contest 2003 (ZOJ1985) ## 题目描述 柱状图是一个多边形，包含一组排列在一条基准线上的矩形。这些矩形宽度一样，但高度可以不一样。例如，下图的左图描绘了一个柱状图包含了一组高度依次为2, 1, 4, 5, 1, 3, 3的矩形，它们的宽度均为1。  给定一个柱状图，计算排列在基准线上的最大矩形的面积。例如，上图右图描绘了该柱状图中的最大矩形。 ## 输入描述 输入数据包含多个测试数据。每个测试数据描述了一个柱状图，首先是一个整数n，代表该柱状图包含的矩形个数，1≤n≤100000。接下来有n个整数$h_{1}$, $h_{2}$, …, $h_{n}$，0≤hi≤100000，这些整数依次（从左到右）代表n个矩形的高度。输入数据最后一行为0，代表输入结束。 ## 输出描述 对每个测试数据，输出一行，为求得的最大矩形的面积。 ## 样例输入 ```txt 7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0 ``` ## 样例输出 ```txt 8 4000 ```