F - -1, +1 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

あなたは以下の操作を A に対して 0 回以上好きな回数行うことができます：

  • 1\le i \le N - 1 を満たす整数 i を選び、A_i を 1 減らし、A_{i+1} を 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 番目 (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

1 番目のテストケースについて考えます。

以下のように操作することで 3 回の操作で A を狭義単調増加列にすることができます：

  • i=1 を選ぶ。A=(-1,2,0) となる。
  • i=2 を選ぶ。A=(-1,1,1) となる。
  • i=2 を選ぶ。A=(-1,0,2) となる。

3 回未満の操作で A を狭義単調増加列にすることはできないので、3 を出力してください。

Score : 525 points

Problem Statement

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.

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.

Input

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

Output

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

Sample Input 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

Sample Output 1

3
5
0
78

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.