题目描述(ID:12267)
标题: 黑匣子
标签:
详情:
我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻,黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令:
ADD(x):把元素x放入黑匣子;GET:把i加1的同时,输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。
下面的表6_4是一个11个命令的例子:
表6_4
  
编号
  
命令
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。
输入格式:
输入文件名为blackbox.in,其中第一行存放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
登录并解答