No submission language available for this problem.

Background

小 A 想裁纸，但没注意裁剪机器的锯齿没对齐，因此裁出来的宽度参差不齐。设锯齿宽度为 $1$ ，小 A 想知道能在现有的这个裁好的纸上，裁出最大矩形面积的纸张是多大。

Description

给定 $n$ 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

例如有 6 个柱状分别为：2 1 5 6 2 3，示例图如下：

      #
    # #
    # #
    # #   #
#   # # # #
# # # # # #
2 1 5 6 2 3

会发现第 3 个和第 4 个柱状组合有最大矩形面积 10 。

Format

Input

第一行一个整数 $n$ , 表示有 $n$ 个柱状。

第二行有 $n$ 个整数，表示从左到右的柱状高度( $a_1, a_2, ... a_n$ )。

Output

一个整数表示当前组合中，最大的矩形面积。

Samples

6
2 1 5 6 2 3

10

2
2 4

4

Limitation

• $1 \leq n \leq 10^5$
• $0 \leq a_i \leq 10^4$