U402645 杀毒器

# usaco原题勿喷

农夫约翰有N个（1≤N≤2⋅10e5）草地，排成一行，其中第i块有一定数量的细菌，与健康草地相差ai（−10e15≤ai≤10e15）。例如，如果ai=−3，那么第i块草地的细菌水平比正常水平低3，需要添加3单位的细菌，使其达到健康水平。 农夫约翰希望确保每块草地都被修复到健康水平的细菌量。方便的是，他拥有两种可以喷洒在他的田地上的杀虫剂，一种是添加细菌的，另一种是除去细菌的。当农夫约翰喷洒任一类型的杀虫剂时，他站在第N块草地（最右边的一块）上，并选择一个功率级别L来设置喷雾器（1≤L≤N）。 喷雾器对离农夫约翰较近的草地影响最大，远离他的地方效果逐渐减弱。如果农夫约翰选择添加细菌的杀虫剂，那么第N块草地将添加L单位的细菌，第N−1块将添加L−1单位，第N−2块将添加L−2单位，依此类推。第1到N−L块将不受影响，因为喷雾器的功率不足以到达它们。同样，如果农夫约翰选择除去细菌的杀虫剂，那么第N块将去除L单位的细菌，第N−1块将去除L−1单位，依此类推。同样，第1到N−L块将不受影响。 找到农夫约翰必须使用喷雾器的最小次数，以使每块草地的细菌量达到健康草地的推荐值。保证答案最多为109。 注意，此问题涉及的整数较大，可能需要使用64位整数数据类型（例如，在C/C++中使用"long long"）。

输入格式（输入从终端/标准输入中获得）： 第一行包含N。 第二行包含N个整数a1…aN，每块草地的初始细菌水平。

输出格式（将输出打印到终端/标准输出）： 使每块草地的细菌量达到健康草地的推荐值所需的最小喷雾次数。