求最大矩形面积

题目描述:

平面上有N个紧凑排成一排的矩形，宽度都为1，给出N个矩形的高度，求由这N个矩形组成的图形包含的最大的矩形面积。

输入格式:

输入若干行，以输入的一个0结束。

每行第一个数n，表示共有n个矩形，该行接下来有用一个空格隔开的n个整数，表示每个矩形的高度。

输出格式:

对每行的n个矩形输出一个答案。

样例输入:

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

样例输出:

8
4000

提示:

1<=n<100,000

时间限制: 1000ms
空间限制: 128MB

---