橘子

题目描述

高桥君面前摆着 $N$ 个盘子排成一列，从左边数第 $i$ 个盘子里放着 $A_i$ 个橘子。

高桥君选择一个满足以下全部 $3$ 个条件的整数组 $(l,r,x)$：

• $1\leq l \leq r \leq N$
• $1 \le x$
• 对满足 $l \leq i \leq r$ 的所有整数 $i$，有 $x \le A_i$

然后，高桥君从第 $l$ 个到第 $r$ 个（含两端）的所有盘子中各取出 $x$ 个橘子吃掉。

当整数组 $(l,r,x)$ 选择适当时，高桥君最多能吃掉多少个橘子？

输入格式

输入按以下格式从标准输入给出：

$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$ 个橘子。

数据范围

• 输入均为整数
• $1 \leq N \leq 10^4$
• $1 \leq A_i \leq 10^5$