问题描述

高桥面前有 $N$ 个盘子，排成一列。从左边开始数，第 $i$ 个盘子上放着 $A_i$ 个橙子。

高桥要选择满足以下条件的三个整数 $(l, r, x)$：

• $1\\leq l \\leq r \\leq N$;
• $1 \\le x$;
• 对于 $l \le i \le r$（包括边界），有 $x \\le A_i$。

然后他会从从左边开始数的第 $l$ 个盘子到第 $r$ 个盘子中，每个盘子取 $x$ 个橙子吃掉。

通过选择使得这个数量最大化的三元组 $(l, r, x)$，他最多能吃多少个橙子呢？

约束条件

• 输入中的所有值都是整数。
• $1 \\leq N \\leq 10^4$
• $1 \\leq A_i \\leq 10^5$

输入

输入数据从标准输入读取，输入格式如下：

$N$ $A_1$ $\\ldots$ $A_N$

输出

打印出高桥最多能吃的橙子数量。

示例输入 1

6
2 4 4 9 4 9

示例输出 1

20

通过选择 $(l,r,x)=(2,6,4)$，他能吃到 $20$ 个橙子。

示例输入 2

6
200 4 4 9 4 9

示例输出 2

200

通过选择 $(l,r,x)=(1,1,200)$，他能吃到 $200$ 个橙子。