题目描述

在一座城市里，有 $N$ 座摩天大楼排成一排，从左到右编号为 $1,2,\dots,N$。
第 $i$ 座大楼的高度为 $A_i$。

现在你想在这些大楼前搭建一个广告牌矩形，要求：

• 广告牌覆盖一段连续的大楼区间 $[l,r]$（$1 \le l \le r \le N$）；
• 广告牌的高度为一个正整数 $h$；
• 为了不被大楼挡住，必须满足对所有 $i \in [l,r]$，都有 $h \le A_i$。

也就是说，广告牌可以看作一个宽度为 $(r-l+1)$、高度为 $h$ 的矩形，完全“贴”在大楼前面，并且不会超过任何一座大楼的高度。

你的目标是让广告牌的面积最大，面积定义为：

请你计算最大可能的广告牌面积。

输入格式

第一行输入一个整数 $N$。
第二行输入 $N$ 个整数 $A_1,A_2,\dots,A_N$。

输出格式

输出一个整数，表示最大广告牌面积。

6
2 4 4 9 4 9

20

Hint

• $1 \le N \le 10^4$
• $1 \le A_i \le 10^5$