1.最大矩阵

题目描述

有$N$个宽度为$1$，高度为$h_{i}$的矩形，设第$i$段到第$j$段的最低高度为$h$，$(j-i+1) \times h$为$i$到$j$的最大矩形，如上图。求$1$到$n$的最大矩形。

输入格式

第一行为一个整数$N$；

第二行为$N$个数，分别为$h_{i}$，表示第$i$段的高度。

输出格式

一个整数，为$1$到$n$的最大矩形。

数据范围与提示

共$25$个测试点。

对于第$1$-$20$个测试点，$1 \leq N \leq 200$，每个点$1$分。

对于第$21$-$22$个测试点，$200 \leq N \leq 1000$，每个点$10$分。

对于第$23$-$25$个测试点，$1000 \leq N \leq 100000$，每个点$20$分。

样例

7
2 1 4 5 1 3 3

8