4290 - 第八课:最大矩形

有n个矩形,从左到右紧邻排成一排,它们的宽度都为1,高度分别分$ h_1, h_2, h_3,... h_n $。现在要求一个面积最大的矩形,它的底边和已知矩形的底边对齐。

例如矩形的高度分别为$ 2, 1, 4, 5, 1, 3, 3 $,如下图所示

15842379183874.png

那么它能构成的最大矩形如右图所示,面积为$ 2 * 4 = 8 $。

输入

输入共一行,首先给出一个整数$ n(1 \le n \le 10^5)$,后面跟着n个整数$ h_1, h_2, h_3,... ,h_n (0 \le h_i \le 10^9)$。

输出

输出一个整数表示答案。

样例

输入

7 2 1 4 5 1 3 3

输出

8

输入

4 1000 1000 1000 1000

输出

4000
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题