该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

空号之后

题目描述

有一排从 $1$ 开始编号的储物柜，编号均为正整数。

现在有 $n$ 个储物柜已经被占用，它们的编号分别为：

这些编号严格递增。

对于一个没有被占用的正整数编号，我们称它为一个空号。

现在有 $q$ 个询问。每个询问给出两个整数 $x,k$，你需要求出：

严格大于 $x$ 的第 $k$ 个空号是多少。

注意：

• $x$ 可以不是被占用的编号；
• $x$ 可以为 $0$；
• 每个询问相互独立。

输入格式

第一行输入两个整数 $n,q$，分别表示已占用编号的数量和询问数量。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示已经被占用的储物柜编号。

接下来 $q$ 行，每行输入两个整数 $x,k$，表示一次询问。

数据范围

对于所有测试数据，保证：

保证每个询问的答案不超过 $9 \times 10^{18}$。

所有输入和输出均在 $64$ 位有符号整数范围内。请使用 $64$ 位整数进行计算。

输出格式

对于每个询问，输出一行一个整数，表示严格大于 $x$ 的第 $k$ 个空号。

输入输出样例 #1

输入 #1

5 6
2 3 7 11 12
0 1
3 2
6 1
7 3
10 2
12 4

输出 #1

1
5
8
10
14
16

说明/提示

在样例中，已经被占用的编号为：

因此空号依次为：

对于询问 7 3，严格大于 $7$ 的空号为：

其中第 $3$ 个是 $10$。

对于询问 12 4，严格大于 $12$ 的空号为：

其中第 $4$ 个是 $16$。