Problem 3. Balancing Bacteria

USACO 2024 January Contest, Bronze

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 选择添加细菌的农药，则 $L$ 单位的细菌将被添加至草地 $N$，$L-1$ 单位添加至草地 $N-1$，$L-2$ 单位添加至草地 $N-2$，以此类推。草地 $1 \ldots N-L$ 不会得到任何细菌，因为喷雾器设置的功率不足以到达它们。类似地，如果 Farmer John 选择去除细菌的农药，则 $L$ 单位的细菌将被从草地 $N$ 去除，$L-1$ 单位被从草地 $N-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

使用去除细菌的农药，功率等级为 1，使用五次。然后使用添加细菌的农药，功率等级为 $2$，使用一次。

输入样例：

5
1 3 -2 -7 5

输出样例：

26

测试点性质： 测试点 3-5：$N \le 10^3$，答案不超过 $10^3$。测试点 6-10：$N \le 10^3$。测试点 11-15：没有额外限制。

供题：Rohin Garg