D - 第K个不在序列中的数

分数：400分

问题描述

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

对于第$i$个查询$(1 \leq i \leq Q)$，给定一个正整数$K_i$，找出与$A_1, A_2, \dots, A_N$中的所有数都不同的第$K_i$个最小的正整数。

约束

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18}$
• $1 \leq K_i \leq 10^{18}$
• 输入中的所有值均为整数。

输入

从标准输入读入以下格式的输入：

$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$、$9$和$4$。

5 2
1 2 3 4 5
1
10

6
15