AT_abc459_f.-1, +1

You are given a sequence of non-negative integers $A = (A_1, A_2, \ldots, A_N)$ of length $N$.

You can perform the following operation on $A$ zero or more times:

• Choose an integer $i$ with $1 \le i \le N - 1$, decrease $A_i$ by $1$, and increase $A_{i+1}$ by $1$.

Find the minimum number of operations required to make $A$ strictly increasing.

It can be proved that the answer is less than $2^{63}$.

You are given $T$ test cases; solve each.

给你一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$。

你可以对 $A$ 执行以下操作零次或多次：

• 选择一个满足 $1 \le i \le N - 1$ 的整数 $i$，将 $A_i$ 减少 $1$，同时将 $A_{i+1}$ 增加 $1$。

求使 $A$ 严格递增所需的最少操作次数。

可以证明答案小于 $2^{63}$。

你将得到 $T$ 组测试用例，请对每组进行求解。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

The $i$-th $(1 \le i \le T)$ test case $\text{case}_i$ is given in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

第 $i$ 个 $(1 \le i \le T)$ 测试用例 $\text{case}_i$ 按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
Consider the first test case.

By performing the following operations, $A$ can be made strictly increasing in three operations:

• Choose $i=1$. $A$ becomes $(-1, 2, 0)$.
• Choose $i=2$. $A$ becomes $(-1, 1, 1)$.
• Choose $i=2$. $A$ becomes $(-1, 0, 2)$.

It is impossible to make $A$ strictly increasing in fewer than three operations, so output $3$.

Constraints

• $1 \le T \le 3 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• The sum of $N$ across all test cases is at most $6 \times 10^5$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。

通过执行以下操作，可在三次操作内使 $A$ 严格递增：

• 选择 $i=1$，$A$ 变为 $(-1, 2, 0)$；
• 选择 $i=2$，$A$ 变为 $(-1, 1, 1)$；
• 选择 $i=2$，$A$ 变为 $(-1, 0, 2)$。

无法用少于三次操作使 $A$ 严格递增，因此输出 $3$。

约束条件

• $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$。
• 所有输入值均为整数。