如果可以从数组 $$$b$$$ 中删除一些元素(可能全部,可能没有)以获得数组 $$$a$$$,则数组 $$$a$$$ 被称为数组 $$$b$$$ 的子序列。
给定一个数组 $$$a = [a_1, a_2, \dots, a_n]$$$。如果满足以下条件,我们称数组 $$$b = [b_1, b_2, \dots, b_m]$$$ 漂亮:
- $$$a$$$ 是 $$$b$$$ 的子序列;
- 对于从$$$1$$$到$$$m-1$$$的每个$$$i$$$,元素$$$b_i$$$和$$$b_{i+1}$$$正好相差$$$1$$$(即$$$|b_i - b_{i+1}| = 1$$$);
- 在满足这两个要求的所有数组中,$$$b$$$的长度是最小的。
您必须处理 $$$q$$$ 查询。在第 $$$i$$$ 查询中,给出了单个整数 $$$x_i$$$。你的任务如下:
- 如果 $$$x_i$$$ 大于漂亮数组中元素的最小可能数量,则打印 $$$-1$$$;
- 否则,如果相同的数字在所有漂亮数组中占据位置$$$x_i$$$,则打印该数字;
- 否则,打印 $$$0$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
第三行包含 $$$q$$$ 整数 $$$x_1, x_2, \dots, x_q$$$ ($$$1 \le x_i \le 10^{18}$$$)。
输出
对于每个查询,打印一个整数 - 它的答案。
示例
输入复制
5 164 1 1 5 91 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
输出复制
4 3 2 1 0 1 2 3 4 5 6 7 8 9 -1 -1