← 返回题目列表

Codeforces · 660/F

F. 熊和保龄球 4

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

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

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

Limak 投了 n 次,第 i 次得到了 ai 分数。他想最大化他的总分,他想出了一个有趣的想法。他可以说,一些第一个滚球只是热身,而他在最后一个滚球期间没有集中注意力。更正式地说,他可以取消序列 a1, a2, ..., an 的任何前缀和后缀。可以取消所有掷骰,也可以不取消任何掷骰。

总得分的计算方式就像只有未取消的骰子一样。因此,第一个未取消的骰子的得分乘以 1,第二个未取消的骰子的得分乘以 2,依此类推,直到最后一个未取消的骰子。

Limak 的最高总分是多少?

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — Limak 生产的卷的总数。

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

输出

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

示例

输入 #1

6
5 -1000 1 -3 7 -8

输出 #1

16

输入 #2

5
1000 1000 1001 1000 1000

输出 #2

15003

输入 #3

3
-60 -70 -80

输出 #3

0

注意

在第一个样本测试中,Limak 应取消前两卷和最后一卷。他的掷骰数为 1、- 3、7,总分为 1·1 + 2·( - 3) + 3·7 = 1 - 6 + 21 = 16。