← 返回题目列表

Codeforces · 573/E

E. 熊和保龄球

中文机器翻译题面 查看原题

Limak 是一只老棕熊。他经常和他的朋友一起去打保龄球。今天他感觉非常好,并试图打破自己的纪录!

对于滚动球,我们会得到一个分数——一个整数(可能是负数)的分数。第 i 卷的分数乘以 i,然后将分数相加。因此,对于分数为 s1、s2、...、sk 的 k 卷,总分数为 $$\sum_{i=1}^{k} i \cdot s_i$$。如果没有掷骰子,则总分为 0。

Limak 投了 n 次,并在第 i 次中得到了分数 ai。他想最大化他的总分,他想出了一个有趣的想法。他会取消一些滚动,说有什么东西分散了他的注意力或者有强风。

Limak 能够取消任意数量的掷骰,甚至可以取消全部或全部。总分的计算就像只有未取消的骰子一样。查看示例测试以进行澄清。 Limak 的最高总分是多少?

输入

第一行包含单个整数 n (1 ≤ n ≤ 105)。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (|ai| ≤ 107) - Limak 掷骰子的分数。

输出

选择要取消的卷后打印可能的最大总分。

示例

输入 #1

5
-2 -8 0 5 -3

输出 #1

13

输入 #2

6
-10 20 -30 40 -50 60

输出 #2

400

注意

在第一个样本中,Limak 应该取消得分为 - 8 和 - 3 的掷骰。然后他剩下得分为 - 2、0、5 的三掷。总得分为 1·( - 2) + 2·0 + 3·5 = 13。

在第二个样本中,Limak 应取消得分为 - 50 的掷骰。总得分为 1·( - 10) + 2·20 + 3·( - 30) + 4·40 + 5·60 = 400。