Migrated from Lutece 3016 开放世界

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

确实是这样的。 但是《暑假前集训》是由UESTC自主研发的一款全新开放世界冒险游戏。 故事背景发生在一个被称作「搜索与动态规划」的世界，在这里，被选中的人将被赋予一个序列，导引子段和之力。 你将扮演一位名为「出题人懒得编了」的神秘角色，在自由的OJ与博客中邂逅方法各异、能力独特的题型们，和它们一起学习算法，找回WA掉代码中的bug——同时，逐步发掘「AC」的真相。

题意：给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，需要选取一段连续的子段 ${a_l,a_{l+1},\cdots,a_r}$ 使得 $\sum_{i=l}^r(i-l+1)\cdot a_i$最大。其中 $l$ 可以大于 $r$，即选择长度为 $0$ 的子段。

Input

第一行一个正整数 $n$，第二行$n$个整数$a_1,a_2,\cdots,a_n$。

Output

一个整数表示答案。

Samples

6
1 -1 4 -5 1 -4

11

5
1 2 3 2 1

27

3
-1 -2 -3

0

Constraints

$1\le n\le 2\times10^5,-10^6\le a_1,a_2,\cdots,a_n\le 10^6$.

Note

对于样例，选取$l=1,r=3$时达到最大值$1\times1 -2\times 1+3\times 4=11$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming