← 返回题目列表

Codeforces · 2199/E

E. 超级序列

中文机器翻译题面 查看原题

如果可以从数组 $$$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 16
4 1 1 5 9
1 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