本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Farmer John 有 $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 个单位的细菌才能达到被认为健康的水平。

Farmer John 想确保每块草地都被纠正到健康的细菌水平。方便的是，他有两种品牌的农药可以喷洒在田地上：一种增加细菌，另一种减少细菌。当 Farmer John 喷洒任意一种农药时，他站在第 $N$ 块草地（最右边）并为喷雾器选择一个功率等级 $L$（$1 \leq L \leq N$）。喷雾器对离 Farmer John 越近的草地影响越大，越远影响越小。

如果 Farmer John 选择增加细菌的农药，则第 $N$ 块草地会增加 $L$ 个单位的细菌，第 $N-1$ 块增加 $L-1$ 个单位，第 $N-2$ 块增加 $L-2$ 个单位，依此类推。第 $1 \ldots N-L$ 块草地不会收到任何细菌，因为喷雾器的功率不足以影响到它们。

类似地，如果 Farmer John 选择减少细菌的农药，则第 $N$ 块草地会减少 $L$ 个单位的细菌，第 $N-1$ 块减少 $L-1$ 个单位，依此类推。同样地，第 $1 \ldots N-L$ 块草地不受影响。

请找出 Farmer John 至少需要喷洒多少次，才能使每块草地都达到健康草地所推荐的细菌水平。保证答案不超过 $10^9$。

注意：本题涉及的整数范围较大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。

输入格式

第一行包含 $N$。 第二行包含 $N$ 个整数 $a_1\dots a_N$，表示每块草地的初始细菌水平。

输出格式

输出使每块草地都达到健康草地所推荐的细菌水平所需的最少喷洒次数。

2
-1 3

6

5
1 3 -2 -7 5

26

提示

使用减少细菌的农药，功率等级为 1，喷洒五次。然后使用增加细菌的农药，功率等级为 $2$，喷洒一次。 SCORING: 测试点 3-5：$N \le 10^3$，答案不超过 $10^3$ 测试点 6-10：$N \le 10^3$ 测试点 11-15：无额外限制。 题目来源：Rohin Garg

来源

USACO|2024|Bronze