\(A_1, A_2, \dots, A_N\) のいずれとも異なる正の整数を良い整数と呼ぶことにします。

各 \(i\) について、\(A_i\) 以下の良い整数の個数 \(C_i\) を記録しておきます。

これを用いると、 小さい方から数えて \(K\) 番目の良い整数は次のように求められます :

• \(C_N < K\) のとき
  • 答えは必ず \(A_N\) より大きいです。\(A_N\) より大きい整数は全て良い整数であるので、 \(A_N + (K - C_N)\) が答えとなります。
• \(C_N \geq K\) のとき
  • \(C_i \geq K\) となる最小の \(i\) を二分探索によって求めると、答えは \(A_{i - 1}\) より大きく、\(A_i\) より小さくなります (ただし、\(A_0 = 0\) とする) 。\(A_{i - 1}\) より大きく \(A_i\) より小さい整数は全て良い整数であるので、\(A_{i} - 1\) から \(C_i - K\) 個戻った \((A_i - 1) - (C_i - K)\) が答えとなります。

計算量は \(O (N + Q \log N)\) です。

実装例 (C++)