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。