黑匣子
题目描述:
我们使用黑匣子的一个简单模型。它能存入一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子有执行一系列的命令。有两类命令：
ADD（X）：把元素X放入黑匣子；GET：把i加1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。
下面的表是一个11个命令的例子：
|
编号 |
命令 |
i |
黑匣子内容 |
输出 |
|
1 |
ADD(3) |
0 |
3 |
|
|
2 |
GET |
1 |
3 |
3 |
|
3 |
ADD(1) |
1 |
1,3 |
|
|
4 |
GET |
2 |
1,3 |
3 |
|
5 |
ADD(-4) |
2 |
-4,1,3 |
|
|
6 |
ADD(2) |
2 |
-4,1,2,3 |
|
|
7 |
ADD(8) |
2 |
-4,1,2,3,8 |
|
|
8 |
ADD(-1000) |
2 |
-1000,-4,1,2,3,8 |
|
|
9 |
GET |
3 |
-1000,-4,1,2,3,8 |
1 |
|
10 |
GET |
4 |
-1000,-4,1,2,3,8 |
2 |
|
11 |
ADD(2) |
4 |
-1000,-4,1,2,2,3,8 |
|
现需要一个有效的算法处理给定的一系列命令。ADD和GET命令总数至多有30000个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面两个整数序列描述命令序列：
（1） A(1)，A(2)，…，A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A＝（3,1，－4,2，8，－1000,2）。
（2） u(1)，u(2)）…，u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1,2,6,6,)。
你可以假定自然数序列u(1),u(2)，…，u(N)以非降序排列，N<=M，且对于每一个p(1<=p<=N)有p<=u(p)<=M。
输入格式:
其中第一行存放M和N的值，第二行存放A(1)，A(2)，…，A(M)，第三行存放u(1)，u(2)）…，u(N)。
输出格式:
输出黑匣子的处理结果。
样例输入:
7 4 3 1 -4 2 8 -1000 2 1 2 6 6
样例输出:
3 3 1 2时间限制: 1000ms
空间限制: 128MB