题目描述

有一个由 $N$ 个 不同整数 组成的列表。列表中第 $i$ 个整数是 $A_i$ 。

有 $Q$ 组询问，每组询问给定两个整数 $X,Y$，你需要求出

• 大于等于 $X$ 且 不在列表中 的第 $Y$ 个整数是多少。

输入格式

第一行输入 $N,Q$。

第二行输入 $A_1,A_2,\ldots,A_N$。

接下来 $Q$ 行，每行输入两个整数 $X,Y$。

输出格式

输出 $Q$ 行，每行一个整数表示答案。

5 4
16 9 2 3 1
6 10
12 4
1 1
1000000000 1000000000

17
15
4
1999999999

10 10
284008711 658403910 982178205 50598815 694147827 230009803 763277509 509451676 821970166 284008710
740250292 159734720
255870361 8400028
23659634 718117163
697334729 301140741
698853172 270344164
713418715 285312509
50065000 52368934
46642556 591869945
607623561 273664826
482426028 265015448

899985013
264270388
741776803
998475472
969197337
998731226
102433934
638512505
881288390
747441478

提示

样例 1 解释

对于第一个询问，大于或等于 $6$ 的最小的 $10$ 个不在列表中的整数是 $6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17$ 。因此，问题的答案是 $17$ 。

对于第二个询问，大于或等于 $12$ 的最小的 $4$ 个整数，不在列表中的是 $12,\ 13,\ 14,\ 15$ 。因此，问题的答案是 $15$ 。

对于第三个询问，在大于或等于 $1$ 的整数中，不在列表中的第 $1$ 个数是 $4$ 。

对于第四个询问，在大于或等于 $1,000,000,000$ 的整数中，不在列表中的第 $1,000,000,000$ 个数是 $1,999,999,999$ 。

数据范围

对于 $100\%$ 的数据满足：$1 \leq N,Q \leq 3 \times 10^5$，$1 \leq A_i \leq 10^9$，保证 $A_1, \dots, A_N$ 互不相同。对于每一次询问满足：$1 \leq X,Y \leq 10^9$。

• 子任务 $1$ （$30$ 分）：$1 \le N, Q \le 2000$，$1 \le A_i, X, Y \le 2000$。
• 子任务 $2$ （$30$ 分）：对于所有的询问，保证 $X = 1$。
• 子任务 $3$ （$40$ 分）：无特殊限制。