← 返回题目列表

AtCoder · abc459_f

F. 减一加一

中文机器翻译题面 查看原题

分数: 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.