题目描述

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

输入格式

第一行为一个数字 $n(1\le n\le 10^5)$。

接下来给出 $n$ 个数字 $h_1,h_2,\cdots, h_n\ (0\le hi\le 10^9)$，表示每个矩形的高度。

输出格式

一个整数，表示最大子矩形面积。

7
2 1 4 5 1 3 3

8

4
1000 1000 1000 1000

4000