Before performing operations, focus on a specific piece.
When the piece in column \(i\) is in row \(R_i\), how does it affect to the other pieces?
Since the pieces can be only moved up, we can derive the following fact:

• The piece in column \(j\) must be located in row \(R_i+|j-i|\) or above.

For example, if the piece is in row \(5\), column \(7\):

• \(\dots\)
• The piece in column \(3\) must be located in row \(9\) or above.
• The piece in column \(4\) must be located in row \(8\) or above.
• The piece in column \(5\) must be located in row \(7\) or above.
• The piece in column \(6\) must be located in row \(8\) or above.
• The piece in column \(7\) must be located in row \(9\) or above.
• \(\dots\)

To propagate these constraints to all columns, follow these steps:

• First, for \(i=2,3,\dots,N\) in order:
  • Set \(R_i = \min(R_i,R_{i-1}+1)\).
• Then, for \(i=N-1,N-2,\dots,1\) in order:
  • Set \(R_i = \min(R_i,R_{i+1}+1)\).

This way, the constraints imposed by each piece can be propagated to all columns.

In fact, the \(R_i\) resulting from the steps above is the optimal row for the final location of the piece in each row (minimizes the number of operations). Therefore, the problem can be answered by subtracting the sum of the resulting \(R\) from the sum of the original \(R\).
Proof:
The discussion above proves the necessity that the piece in column \(R_i\) must be located in row \(R_i\) or above. Thus, the proof is completed by showing the sufficiency, that is, placing the pieces according to the resulting \(R\) satisfies the condition—all adjacent elements in \(R\) differ at most by one.

When the former loop ends, \(R_{i-1}+1 \ge R_i\) for all \(i=2,3,\dots,N\).
Now let us inspect the latter loop.

• The loop progresses as \(i=N-1,N-2,\dots,1\).
  • Focus on the operation \(R_i = \min(R_i,R_{i+1}+1)\).
  • If \(R_i\) has been updated by this operation, then \(R_i = R_{i+1}+1\), so \(R_i\) and \(R_{i+1}\) differ by one.
  • If \(R_i\) has not been updated by this operation, we have \(R_i \le R_{i+1}+1\) after the operation. However, the former loop guarantees that \(R_i +1 \ge R_{i+1}\), and updating \(R_{i+1}\) in the latter loop always makes \(R_{i+1}\) smaller, so this inequality is never violated. Combining the two inequalities, we obtain \(R_{i+1}-1 \le R_i \le R_{i+1}+1\), proving that \(R_i\) and \(R_{i+1}\) differ at most by one.

Hence, it has been shown that the placements of the pieces according to the \(R\) resulting from the two loops satisfy condition in the problem statement. This concludes the proof.

This solution runs in \(O(N)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll t;
  cin >> t;
  while(t--){
    ll n,s=0;
    cin >> n;
    vector<ll> r(n);
    for(auto &nx : r){
      cin >> nx;
      s+=nx;
    }
    for(ll i=1;i<n;i++){ r[i]=min(r[i],r[i-1]+1); }
    for(ll i=n-2;i>=0;i--){ r[i]=min(r[i],r[i+1]+1); }
    for(auto &nx : r){ s-=nx; }
    cout << s << "\n";
  }
  return 0;
}