题目描述

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

你可以对 $A$ 执行任意次如下操作：

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

求最少需要执行多少次操作，才能使 $A$ 成为一个严格递增序列。

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

本题有 $T$ 组测试数据，请对每组数据分别求解。

输入格式

第一行一个整数 $T$，表示测试组数。

接下来依次给出每组测试数据。

每组测试数据的格式如下：

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

输出格式

对于每组测试数据，输出一行一个整数，表示最少操作次数。

数据范围

• $1 <= T <= 3 * 10^5$
• $1 <= N <= 2 * 10^5$
• $0 <= A_i <= 10^9$
• 所有测试数据中的 $N$ 之和不超过 $6\times 10^5$
• 输入中的所有值均为整数

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

3
5
0
78

样例说明

考虑第一组数据。

可以按如下方式操作三次，使 $A$ 变为严格递增：

1. 选择 $i=1$，序列变为 $(-1, 2, 0)$。
2. 选择 $i=2$，序列变为 $(-1, 1, 1)$。
3. 再次选择 $i=2$，序列变为 $(-1, 0, 2)$。

可以证明少于 $3$ 次操作无法做到，因此答案为 $3$。

来源

• AtCoder Beginner Contest 459
• 原题链接：https://atcoder.jp/contests/abc459/tasks/abc459_f