题目描述

给定一个长度为 $N$ 的整数序列 $A$。接下来有 $Q$ 个询问，每个询问给出一个整数 $k$，你需要回答整个序列中第 $k$ 小的数。

本题用于练习整体二分的最基础形态：所有询问的判定区间相同，只需在值域上不断把询问分到左半或右半。

输入格式

第一行两个整数 $N, Q$。

第二行 $N$ 个整数 $A_i$。

第三行 $Q$ 个整数 $k_i$。

输出格式

输出 $Q$ 行，第 $i$ 行为第 $i$ 个询问的答案。

数据范围

• $1 \le N,Q \le 2 \times 10^5$
• $-10^9 \le A_i \le 10^9$
• $1 \le k_i \le N$

5 5
5 1 3 3 9
1 2 3 4 5

1
3
3
5
9