Kth Excluded

题目描述

给出一个由 $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$ 小的整数。

输入格式

输入按照下列格式自标准输入给出： $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

5 2
1 2 3 4 5
1
10

6
15

提示

$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}$ 输入中的所有数值均为整数。与所有 $A_1, A_2, \dots, A_N$ 不同的正整数按升序为 $1, 2, 4, 8, 9, 10, 11, \dots$。 它们的第 2、5 和第 3 小分别是 $2$、$9$ 和 $4$。

标签: AtCoder|abc205D

来源

AtCoder|abc205D