题目描述

WFYZ有很多花坛， $N$（$1\le N\le 2\cdot 10^5$）个花坛排成一行，小容是管理员，她发现其中花坛 $i$ 的营养水平与健康花的营养水平相差 $a_i$（$−10^{15}\le a_i\le 10^{15}$）。例如，如果 $a_i=−3$，则花坛 $i$ 的营养水平比正常水平低 $3$，需要额外添加恰好 $3$ 个单位的营养才能将其提高到被认为是健康的程度。

小容想要确保每一个花坛都被修复至健康的营养水平。方便的是，她有两种品牌的养护剂可以喷洒在她的花园里，一种可以添加营养，另一种可以去除营养。当小容喷洒任一类型的养护剂时，她站在花坛 $N$（最右边的花坛）并为她的喷雾器选择功率等级 $L$（$1\le L\le N$）。

喷雾器对靠近小容的花坛效果最大，随着距离增加效果逐渐减弱。如果小容选择添加营养的养护剂，则 $L$ 单位的营养将被添加至花坛 $N$，$L−1$ 单位添加至花坛 $N−1$，$L−2$ 单位添加至花坛 $N−2$，以此类推。花坛 $1\ldots N−L$ 不会得到任何营养，因为喷雾器设置的功率不足以到达它们。类似地，如果小容选择去除营养的养护剂，则 $L$ 单位的营养将被从花坛 $N$ 去除，$L−1$ 单位被从花坛 $N−1$ 去除，以此类推。同样，花坛 $1\ldots N−L$ 将不受影响。

求小容使用喷雾器的最少次数，使得每个花坛都具有健康花的推荐营养值。输入保证答案不超过 $10^9$。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $a_1\ldots a_N$，为每个花坛的初始营养水平。

输出格式

输出一个整数，为使每个花坛都具有健康花的推荐的营养值所需使用喷雾器的最少次数。

输入输出样例 #1

输入 #1

2
-1 3

输出 #1

6

输入输出样例 #2

输入 #2

5
1 3 -2 -7 5

输出 #2

26

说明/提示

样例解释 1

使用去除营养的养护剂，功率等级为 $1$，使用五次。然后使用添加营养的养护剂，功率等级为 $2$，使用一次。

测试点性质

• 对$20\%$的数据：$N\le 10^3$，答案不超过 $10^3$。
• 对$60\%$的数据：$N\le 10^3$。
• 对$100\%$的数据$：没有额外限制。