まず、操作を行う前に、ある特定の駒に注目してみましょう。
\(i\) 列目の \(R_i\) 行目に駒があることで、他の駒にはどのような影響が出るでしょうか？
駒は上にしか動けないことに注意すると、以下の事実を導くことができます。

• \(j\) 列目にある駒は、 \(R_i+|j-i|\) 行目かそれより上に存在しなければならない。

例えば、 \(5\) 列目の \(7\) 行目に駒があるとき、

• \(\dots\)
• \(3\) 列目にある駒は \(9\) 行目かそれより上に存在しなければならない。
• \(4\) 列目にある駒は \(8\) 行目かそれより上に存在しなければならない。
• \(5\) 列目にある駒は \(7\) 行目かそれより上に存在しなければならない。
• \(6\) 列目にある駒は \(8\) 行目かそれより上に存在しなければならない。
• \(7\) 列目にある駒は \(9\) 行目かそれより上に存在しなければならない。
• \(\dots\)

というような制約がかかることになります。
そして、このような制約を全ての列について高速に伝播させるためには、以下の手順を取ればよいです。

• まず、 \(i=2,3,\dots,N\) について順に、以下を行う。
  • \(R_i = \min(R_i,R_{i-1}+1)\) に更新する。
• 次に、 \(i=N-1,N-2,\dots,1\) について順に、以下を行う。
  • \(R_i = \min(R_i,R_{i+1}+1)\) に更新する。

こうすることで、全ての駒について、その駒から生じる制約を全ての列に伝播することができることが分かります。

そして、実は、上記の手順で更新した \(R_i\) が、最終的に各列の駒が存在する最適 ( 操作回数が最小となる ) な行となります。よって、更新前の \(R\) の総和から更新後の \(R\) の総和を引いた値を出力することでこの問題に正解できます。
証明:
上記の議論より、 \(i\) 列目の駒が \(R_i\) 行目かそれより上にある必要性は導かれました。よって、現時点での \(R\) に従って駒を配置すれば条件を満たすこと、即ち、 \(R\) の全ての隣接要素の差が \(1\) 以下となることを示せば十分性が示されて証明が完了します。

最初のループが完了した際、 全ての \(i=2,3,\dots,N\) について、 \(R_{i-1}+1 \ge R_i\) が満たされます。
では、 \(2\) 回目のループを追跡しましょう。

• \(i=N-1,N-2,\dots,1\) の順で進行する。
  • \(R_i = \min(R_i,R_{i+1}+1)\) という操作に着目する。
  • もし \(R_i\) がこの操作により更新された場合、 \(R_i = R_{i+1}+1\) に更新されているため、 \(R_i\) と \(R_{i+1}\) との差は \(1\) である。
  • もし \(R_i\) がこの操作により更新されなかった場合、操作後の時点で \(R_i \le R_{i+1}+1\) となっている。但し、最初のループの時点で \(R_i +1 \ge R_{i+1}\) となっており、その後 \(2\) 回目のループで \(R_{i+1}\) が更新されたとしても \(R_{i+1}\) は小さくなるだけなのでこの不等式は揺るがない。よって、 \(2\) つの不等式を統合すると \(R_{i+1}-1 \le R_i \le R_{i+1}+1\) が得られ、 \(R_i\) と \(R_{i+1}\) との差が高々 \(1\) であると分かる。

以上より、 \(2\) 回のループを回した後の \(R\) に従った駒の配置は問題文中の条件を満たすことが分かり、証明が完了しました。

本解法の時間計算量は \(O(N)\) です。

実装例 (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;
}