4327: 【基础】刷广告(1773)

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

最近,afy 决定给 TOJ 印刷广告,广告牌是刷在城市的建筑物上的,城市里有紧靠着的 lns="http://www.w3.org/1998/Math/MathML"> 个建筑。

afy 决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度,从左到右给出每个建筑物的高度lns="http://www.w3.org/1998/Math/MathML">1,2,,,且 lns="http://www.w3.org/1998/Math/MathML">0<109,并且我们假设每个建筑物的宽度均为 lns="http://www.w3.org/1998/Math/MathML">1 。

要求输出广告牌的最大面积。

输入

第一行是一个整数 lns="http://www.w3.org/1998/Math/MathML"> (lns="http://www.w3.org/1998/Math/MathML">400,000)。

第二行是 lns="http://www.w3.org/1998/Math/MathML"> 个数,分别表示每个建筑物高度lns="http://www.w3.org/1998/Math/MathML">1,2,,,且 lns="http://www.w3.org/1998/Math/MathML">0<109

输出

一个整数,表示最大面积。

样例输入 复制

6
5 8 4 4 8 4

样例输出 复制

24

提示

【样例解释】

样例数据的中,最大广告牌的安装方法如下图所示。