Binary Trieでも解けます。

Binary Trieは値に追加する数の最大値を\(A\)として例えば以下のことが\(O(\rm{log}(A))\)でできるデータ構造です

• 値の追加
• 値の削除
• \(x\)未満の値の個数の取得
• \(k\)番目に小さい値の取得

今回の問題では、「\(x\)未満の値の個数の取得」で、求める値が全体で何番目に小さい値かが分かるので、「\(k\)番目に小さい値の取得」で求める値を得ることで、\(k>5\)の場合でも\(O(Q\rm{log}(x_{max}))\)で答えを求めることができます。

実装例(pypy)