描述

我们的“黑匣子”代表一个原始数据库。它可以保存一个整数数组，并且有一个特殊的变量$i$。在初始时刻，黑匣子为空，且$i$等于$0$。这个黑匣子处理一系列的命令（事务）。有两种类型的事务：

添加（ADD）（$x$）：将元素$x$放入黑匣子中；

获取（GET）：将$i$增加$1$，并从黑匣子中包含的所有整数中给出第$i$小的数。请记住，第$i$小的数是在黑匣子中的元素按非降序排序后位于第$i$个位置的数。

让我们研究一个可能的由$11$个事务组成的序列：

示例1

需要设计出一种高效的算法来处理给定的事务序列。“添加（ADD）”和“获取（GET）”事务的最大数量：每种类型各为$30000$个。

让我们用两个整数数组来描述事务序列：

1. $A(1), A(2), \ldots, A(M)$：一系列正被放入黑匣子的元素。$A$的值是绝对值不超过$2000000000$的整数，$M \leq 30000$。对于上述示例，我们有$A = (3, 1, -4, 2, 8, -1000, 2)$。

2. $u(1), u(2), \ldots, u(N)$：一个序列，它设定了在第$1$次、第$2$次、……以及第$N$次“获取（GET）”事务时正被放入黑匣子的元素数量。对于上述示例，我们有$u = (1, 2, 6, 6)$。

黑匣子算法假定自然数序列$u(1), u(2), \ldots, u(N)$按非降序排列，$N \leq M$，并且对于每个$p$（$1 \leq p \leq N$），不等式$p \leq u(p) \leq M$成立。这是因为对于我们的$u$序列中的第$p$个元素，我们执行一次“获取（GET）”事务，从我们的$A(1), A(2), \ldots, A(u(p))$序列中给出第$p$小的数。

输入 输入包含（按给定顺序）：$M$，$N$，$A(1)$，$A(2)$，……，$A(M)$，$u(1)$，$u(2)$，……，$u(N)$。所有数字由空格和（或）换行符分隔。

输出 根据给定的事务序列，将黑匣子的答案序列写入输出，每个数字占一行。

输入数据 1

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

输出数据 1

3
3
1
2

来源

1996年东北欧竞赛