本解説では，公式解説と同様に，\(A_i\) を \(A_i-i\) に置き換え，狭義単調増加の条件を広義単調増加の条件に変換する．以降は，この変換後の列をブロックの併合として扱う．複数の要素を \((\text{長さ},\ \text{合計})\) のブロックとして管理し，隣り合うブロックが条件に反している間，併合していく．

操作は，ある位置 \(i\) の値を \(1\) 減らし，位置 \(i+1\) の値を \(1\) 増やす操作である．値を左から右へ \(1\) だけ移動する操作と見なせる．最終的に得られる列を \(C\) とする．目標は，次を満たす \(C\) を作ることである．

\[ C_1 < C_2 < \cdots < C_N \]

\(C_i < C_{i+1}\) は \(C_i - i \le C_{i+1} - (i+1)\) と同値である．\(B_i = C_i - i\) とおくと，\(C\) が狭義単調増加であることは，\(B\) が広義単調増加であることと同値である．元の列に対して \(A_i - i\) を考え，これを広義単調増加な列に変形する問題として考える．

数列をブロックの列で表現する．各ブロックは \((\text{長さ},\ \text{合計})\) として管理する．数列が広義単調増加であるためには，ブロック内が広義単調増加であり，かつ隣接するブロック間も広義単調増加であればよい．後者は換言すると，

\[ \text{左ブロックの最大値} \le \text{右ブロックの最小値} \]

であればよい．ブロック全体として隣接条件を満たすためには，ブロック内を広義単調増加にしたうえで，最小値をできるだけ大きく，最大値をできるだけ小さくしたい．そのため，ブロック内の値を平均にできるだけ近づけ，値の差が高々 \(1\) になる形で復元するのが最適である．具体的には，ブロックの長さを \(length\)，合計を \(s\) とすると，

\[ q = \left\lfloor \frac{s}{length} \right\rfloor,\quad r = s - q\times length \]

として，

\[ \underbrace{q,\ldots,q}_{length-r\text{ 個}}, \underbrace{q+1,\ldots,q+1}_{r\text{ 個}} \]

と復元すればよい．ここで，\(r\) は \(s\) を \(length\) で割った余りである．このとき，ブロックの最小値は \(\left\lfloor \frac{s}{length} \right\rfloor\)，最大値は \(\left\lceil \frac{s}{length} \right\rceil\) である．左ブロックを \((length_L, s_L)\)，右ブロックを \((length_R, s_R)\) とすると，

\[ \left\lceil \frac{s_L}{length_L} \right\rceil > \left\lfloor \frac{s_R}{length_R} \right\rfloor \]

のとき，これらのブロックは条件に反しているので併合する．

処理はスタックで行う．空のリストから始め，左から順に \(A_i - i\) を長さ \(1\)，合計 \(A_i - i\) のブロックとして追加する．追加後，末尾 \(2\) つのブロックが広義単調増加の条件に反している間，それらを併合する．併合後のブロックの長さと合計は，それぞれ単純に足せばよい．この処理により，最終的に隣接するすべてのブロックについて条件が満たされる．

スタックに残った各ブロックについて，長さ \(length\)，合計 \(s\) から \(q = \left\lfloor \frac{s}{length} \right\rfloor,\ r = s - q\times length\) を計算し，\(q\) を \(length-r\) 個，\(q+1\) を \(r\) 個並べる．これにより，広義単調増加な列 \(B\) が復元できる．求めたい最終列 \(C\) は \(C_i = B_i + i\) である．

操作回数は，各境界を通過した個数の総和である．境界 \(i\)，つまり \(i\) と \(i+1\) の間を右へ \(1\) 個通過するたびに，左側 prefix の合計

\[ A_1 + A_2 + \cdots + A_i \]

は \(1\) 減る．したがって，境界 \(i\) を右へ通過した個数は

\[ \text{元の prefix 和} - \text{最終列の prefix 和} \]

で求められる．これをすべての境界について足せば，総操作回数になる．

各要素は最初に \(1\) 回スタックに追加される．併合が起きるたびにブロック数は \(1\) 減るため，併合回数は全体で高々 \(N-1\) 回である．各テストケースあたりの計算量は \(\mathcal{O}(N)\) 時間である．

Python による実装例

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    stack = []
    for i in range(n):
        stack.append([1, a[i] - i])
        while len(stack) > 1:
            l0, s0 = stack[-2]
            l1, s1 = stack[-1]
            if (s0 + l0 - 1) // l0 <= s1 // l1:
                break
            stack.pop()
            stack.pop()
            stack.append([l0 + l1, s0 + s1])

    b = []
    for length, s in stack:
        q = s // length
        r = s - q * length
        for _ in range(length - r):
            b.append(q)
        for _ in range(r):
            b.append(q + 1)

    c = [b[i] + i for i in range(n)]

    ans = 0
    sum_a = 0
    sum_c = 0
    for i in range(n - 1):
        sum_a += a[i]
        sum_c += c[i]
        ans += sum_a - sum_c
    print(ans)