题目描述

在平面上有 $n$ 个排成一条直线的矩形，每个矩形的宽度都为 $1$，给定每个矩形的高度 $a_i$，求包含于这些矩形的最大子矩形面积。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一个整数代表最大子矩形的面积。

7 
2 1 4 5 1 3 3

8

6
5 8 4 4 8 4

24

样例 1 解释

提示

对于 $100\%$ 的数据，$1 \le n\leq 1\times 10^6$，$1\leq a_i\leq 10^8$。