该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x10基本数据结构（0x11 栈）例题4：Largeset Rectangle in a Histogoram SP1805 HISTOGRA - Largest Rectangle in a Histogram

SP1805 HISTOGRA - Largest Rectangle in a Histogram

题目背景

如遇 SPOJ 评测服务不稳定，可以在 https://www.luogu.com.cn/problem/B4273 评测本题，注意 $n$ 和 $h_i$ 范围的小变化。

题目描述

如图所示，在一条水平线上有 $n$ 个宽为 $1$ 的矩形，求包含于这些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

8
4000