题目描述

如图，有 $n$ 条面积为 $1 \times h_i$ 的小木棒依次排在一起。现在木匠想在其中取一块矩形来作为工件，问工件最大面积可能是多少？

图例显示了由高度为 2, 1, 4, 5, 1, 3, 3 的木条组成的图形，最大面积如阴影所示。

输入格式

第一行一个整数 $N$，表示木条数量。

第二行有 $N$ 个整数，表示每根木条的高度 $h_i$。

输出格式

输出一个整数，表示能构成的矩形的最大面积。

样例输入

10
1 2 3 4 5 6 7 8 9 10

样例输出

30

数据范围

• 40% 的数据：$1 \leq N \leq 1000$，$0 \leq h_i \leq 10^9$
• 100% 的数据：$1 \leq N \leq 100000$，$0 \leq h_i \leq 10^9$

限制

• 时间限制：1 秒
• 空间限制：256 MB