C - 橘子

分数 : $300$ 点

问题描述

在高桥前面有 $N$ 个盘子，它们排成一排。第 $i$ 个盘子上有 $A_i$ 个橘子。

高桥将选择符合以下条件的三元组 $(l, r, x)$ ：

• $1\leq l \leq r \leq N$；
• $1 \le x$；
• 对于从 $l$ 到 $r$（包括两端）之间的每个整数 $i$ ，有 $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$

输出

打印高桥最多能够吃的橘子的数量。

6
2 4 4 9 4 9

20

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

6
200 4 4 9 4 9

200

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