We use 0-based indexing in this editorial.

By replacing \(A_i\) with \(A_i-i\), the task of making \(A\) strictly increasing becomes a task making \(A\) weakly increasing. Hereinafter, we will consider the minimum number of operations required to make \(A\) weakly increasing.

Let \(B\) be the resulting sequence of \(A\). \(B\) can be uniquely determined.

Since it is obviously optimal to perform the operations greedily from the front elements, the answer is obtained by repeating the following operation while \(A\) is not weakly increasing:

• Choose the minimum \(i\) with \(A_i > A_{i+1}\), and perform the operation.

Moreover, if \(i=0,1,\ldots,N-2\) are all chosen, \(\displaystyle B_i=\left\lfloor\frac{S+i}{N} \right\rfloor\), where \(\displaystyle S=\sum_{i=0}^{N-1} A_i\).

Thus, there exists an integer sequence \(C=(C_0,C_1,\ldots,C_M)\) satisfying the following condition, and \(C\) is unique under the assumption that \(M\) is maximum:

• \(0=C_0 < C_1 < \ldots < C_M=N\).
• For \(0\le k <M,\ i \in [C_k,C_{k+1})\) let \(\displaystyle S_k=\sum_{j=C_k}^{C_{k+1}-1}A_j\). Then \(\displaystyle B_i=\left\lfloor \frac{S_k+i-C_k}{C_{k+1}-C_k}\right\rfloor\).

Intuitively, it claims that one can “flatten” each segment of \(A\) determined by \(C\) to make it weakly increasing.

This \(C\) can be constructed by greedily extending the segment from the front while \(B\) is not weakly increasing.

The problem can be solved by appropriately implementing the algorithm above. The complexity is \(O(N)\).

Sample code (Python 3)

from collections import deque
import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] -= i
    d = deque()
    for v in a:
        now = (1, v)
        while d:
            tail = d[-1]
            if (tail[1] + tail[0] - 1) // tail[0] <= now[1] // now[0]:
                break
            now = (now[0] + tail[0], now[1] + tail[1])
            d.pop()
        d.append(now)
    b = []
    for v in d:
        len, s = v
        for i in range(len):
            b.append((s + i) // len)
    for i in range(n - 1):
        assert b[i] <= b[i + 1]
    ans = 0
    for i in range(n):
        ans += i * (b[i] - a[i])
    print(ans)