AT_abc459_f [ABC459F] -1, +1

長さ $ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 以下のように操作することで $ 3 $ 回の操作で $ A $ を狭義単調増加列にすることができます： - $ i=1 $ を選ぶ。 $ A=(-1,2,0) $ となる。 - $ i=2 $ を選ぶ。 $ A=(-1,1,1) $ となる。 - $ i=2 $ を選ぶ。 $ A=(-1,0,2) $ となる。 $ 3 $ 回未満の操作で $ A $ を狭義単調増加列にすることはできないので、 $ 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 $ - 全てのテストケースにおける $ N $ の総和は $ 6\times 10^5 $ 以下 - 入力される値は全て整数