この問題では、 \(i,i+1,\dots,M\) 番目の本に対する質問が、全ての \(i\) について行われます。
ここで、本の順番を逆順にすると \(1,2,\dots,i\) 番目の本に関する質問となるので、扱いやすくなります。

結局、この問題は以下の形になりました。

• \(1,2,\dots,i-1\) 番目の本について、戻すべき棚の番号が \(G_i\) 未満であるものの冊数を数える。

これは、例えば segment tree を利用して質問と追加を交互に繰り返すことで解くことができます。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using ll=long long;

ll op(ll a,ll b){return (a+b);}
ll e(){return 0;}

int main(){
  ll N,M;
  cin >> N >> M;
  vector<ll> G(M);
  for(auto &nx : G){cin >> nx;}

  segtree<ll,op,e> seg(N+5);
  ll res=0;
  for(ll i=M-1;i>=0;i--){
    res+=seg.prod(0,G[i]);
    seg.set(G[i],seg.get(G[i])+1);
  }
  cout << res << "\n";
  return 0;
}