AT_abc440_d [ABC440D] Forbidden List 2

There is a list consisting of $ N $ distinct integers. The $ i $ -th ( $ 1 \leq i \leq N $ ) integer in the list is $ A_i $ . You are given $ Q $ questions; answer each of them. The $ j $ -th question ( $ 1 \leq j \leq Q $ ) is as follows: - Find the $ Y_j $ -th smallest value among the integers greater than or equal to $ X_j $ that are not in the list.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ \cdots $ $ A_N $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_Q $ $ Y_Q $

Output $ Q $ lines. The $ j $ -th line ( $ 1 \leq j \leq Q $ ) should contain the answer to the $ j $ -th question.

### Sample Explanation 1 For the first question, the smallest $ 10 $ integers greater than or equal to $ 6 $ that are not in the list are $ 6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17 $ . Thus, the answer to the question is $ 17 $ . For the second question, the smallest $ 4 $ integers greater than or equal to $ 12 $ that are not in the list are $ 12,\ 13,\ 14,\ 15 $ . Thus, the answer to the question is $ 15 $ . For the third question, the $ 1 $ st smallest value among the integers greater than or equal to $ 1 $ that are not in the list is $ 4 $ . For the fourth question, the $ 1\,000\,000\,000 $ -th smallest value among the integers greater than or equal to $ 1\,000\,000\,000 $ that are not in the list is $ 1\,999\,999\,999 $ . ### Constraints - $ 1 \leq N \leq 3 \times 10^5 $ - $ 1 \leq Q \leq 3 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - $ A_1, \dots, A_N $ are distinct. - $ 1 \leq X_j \leq 10^9 $ ( $ 1 \leq j \leq Q $ ) - $ 1 \leq Y_j \leq 10^9 $ ( $ 1 \leq j \leq Q $ ) - All input values are integers.