Let us call an integer good if it is different from either of \(A_1, A_2, \dots, A_N\).

For each \(i\), find the number of good integers less than or equal to \(A_i\) and record them as \(C_i\).

Then, the \(K\)-th smallest good integer can be found as follows:

• If \(C_N < K\)
  • The answer is always greater than \(A_N\). Since every integer greater than \(A_N\) is a good integer, the answer is \(A_N + (K - C_N)\).
• If \(C_N \geq K\)
  • Find with binary search the minimum \(i\) such that \(C_i \geq K\), then the answer is greater than \(A_{i - 1}\) and less than \(A_i\) (where we assume \(A_0 = 0\)). Since every integer greater than \(A_{i - 1}\) and less than \(A_i\) is a good integer, the answer is \((A_i - 1) - (C_i - K)\), that is, \(C_i - K\) elements before \(A_{i} - 1\).

The complexity is \(O (N + Q \log N)\).

Sample code (C++)