第 K 个未出现的数

题目描述

给定一个由 $N$ 个正整数组成的数列 $A=(A_1,A_2,\dots,A_N)$，以及 $Q$ 个查询。

在第 $i$ 个查询（$1 \le i \le Q$）中，给定正整数 $K_i$，求与 $A_1,A_2,\dots,A_N$ 都不同的正整数中第 $K_i$ 小的数。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$K_1$
$K_2$
$\vdots$
$K_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

样例

4 3
3 5 6 7
2
5
3

2
9
4

与所有 $A_1,A_2,\dots,A_N$ 都不同的正整数按升序排列为 $1,2,4,8,9,10,11,\dots$。

其中第 2 小、第 5 小、第 3 小的数分别为 $2$、$9$、$4$。

5 2
1 2 3 4 5
1
10

6
15

数据范围

• $1 \le N, Q \le 10^5$
• $1 \le A_1 \lt A_2 \lt \dots \lt A_N \le 10^{18}$
• $1 \le K_i \le 10^{18}$
• 输入均为整数