収納スペースの数 \(N \le 2 \times 10^5\) なので、大きさ \(O(N)\) のデータ構造を利用することができそうです。

求めるべきは、収納スペース \(S_i\) を埋める時点で収納スペース \(1,2,\dots,S_i\) のうちいくつが埋まっているかです( \(S_i\) は埋まっていないことが保証されているので、求める範囲を収納スペース \(S_i-1\) までとしても構いません)。

これは、例えば segment tree を使うことで求めることができます。

実装例 (C++):

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

using namespace std;
using namespace atcoder;

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

int main(){
  int N,M;
  cin >> N >> M;
  segtree<int,op,e> seg(N+1);
  for(int i=0;i<M;i++){
    int S;
    cin >> S;
    cout << S-seg.prod(0,S) << "\n";
    seg.set(S,1);
  }
  return 0;
}