分数: 300 点
问题陈述
有 N 菜肴在高桥面前排列成一排。的 i左起第一个菜有 A_i 橙子就可以了。
Takahashi 将选择整数的三元组 (l, r, x) 满足以下所有条件:
- 1\leq l \leq r \leq N;
- 1 \le x;
- 对于每个整数 i 之间 l 和 r (含), x \le A_i.
然后他会捡起来吃 x 橙子来自每个 l-th 至 r左数第盘菜。
选择三重他最多可以吃多少个橙子 (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 橙子。