402007 - 最大矩形面积

如图2.9所示，给定从左到右多个矩形，已知矩形的宽度都为1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形。 所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。

输入包含多组数组，每组数据有一个整数n（1≤n≤500 000），表示矩阵数量，接下来n个数h1，…，hn，（0≤hi≤1 000 000 000），表示从左到右的矩阵高度，所有数据结束以0表示。

每一组数据输出最大矩形面积。