g++ 拡張でも解けます。

次の要件を満たすデータ構造があればこの問題を解くことができます。

• (多重)集合 $S$ に $X$ を追加する。
• $S$ のうち $X$ 以上となるのが何番目かを求める。
• $S$ のうち $X$ 番目の値を求める。

これらのクエリは、g++拡張によって使える tree というデータ構造を使うことで効率的に処理することができます。

このデータ構造はC++のsetの上位互換のような感覚で、(多重でない)集合において $k$ 番目の値を返すことや $k$ 未満の数が何個あるかを知ることができます。
参考記事
参考記事

ただし、今回の問題では追加する整数 \(x\) が同じ値を含む可能性があるのでそのままではうまくいきません。そこで、追加する整数と追加するタイミングからなるpairを \(S\) に追加することで \(S\) が多重集合になることはなく、treeを使ってこの問題を解くことができます。

実装例