Wavelet 行列を使う、二分探索をしない解法です。

各出力クエリを \(A\) に関する range_freq クエリとみなすところまでは https://atcoder.jp/contests/abc324/editorial/7403 と同じです。加えて \(A\) の逆置換を取っておくことで、クエリ 1 の分割点は二分探索を用いることなく quantile で取得することができます。これにより \(O ( (N + Q) \log N)\) 時間で解くことができます。