g++拡張のtree を用いても楽に実装できます。
この方法は、収納スペースの数 \(N\) がより大きい場合でも適用可能です。

実装例 (C++):

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>

using namespace __gnu_pbds;
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;
  for(int i=0;i<M;i++){
    int S;
    cin >> S;
    cout << S-tr.order_of_key(S) << "\n";
    tr.insert(S);
  }
  return 0;
}