分数: 525 点
问题陈述
给你一个非负整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N.
您可以对 A 零次或多次:
- 选择一个整数 i 与 1 \le i \le N - 1,减少 A_i by 1,并增加 A_{i+1} by 1.
求出需要进行的最少操作次数 A 严格增加。
可以证明答案小于 2^{63}.
你被给予 T 测试用例;逐一解决。
约束
- 1 \le T \le 3 \times 10^5
- 1 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 总和 N 在所有测试用例中最多 6 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
的 i-th (1 \le i \le T) 测试用例 \text{case}_i 按以下格式给出:
N A_1 A_2 \ldots A_N
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
4 3 0 1 0 4 4 6 3 5 7 1 2 3 4 5 6 7 10 11 9 1 3 17 19 10 19 17 3
示例输出 1
3 5 0 78
考虑第一个测试用例。
通过执行以下操作, A 可以通过三种操作进行严格递增:
- 选择 i=1. A 变为 (-1, 2, 0).
- 选择 i=2. A 变为 (-1, 1, 1).
- 选择 i=2. A 变为 (-1, 0, 2).
不可能使 A 严格增加少于三个操作,因此输出 3.