题目内容

有一批货物 $A$ 会按顺序进入仓库，第 $i$ 件货物的价格是 $A[i]$。

管理员会发起一组查询请求 $B$，对于第 $j$ 次查询，你需要回答：在当前已经进入仓库的前 $B[j]$ 件货物中，按价格从小到大排序后，第 $j$ 位的价格是多少。

题目保证所有查询合法，也就是说在第 $j$ 次查询时，当前货物数量不少于 $j$。

其中 $1 \le j \le B[j] \le 5000$，$1 \le A[i] \le 1000000$。

输入描述

• 参数 $1$：整数 $n$，表示货物数量；
• 参数 $2$：整数 $m$，表示查询次数；
• 参数 $3$：一组货物价格的列表 $A$，其中元素 $A[i]$ 表示货物的价格；
• 参数 $4$：一组查询指令列表 $B$，其中元素 $B[j]$ 表示第 $j$ 次查询的货物范围区间。

输出描述

一个数组，其中每个元素为查询列表 $B$ 中，每次指令查询的价格结果。

样例1

输入

7,4,[9,7,2,8,14,1,8],[1,2,6,6]

输出

[9,9,7,8]

说明

• 一共有 7 件货物依次进入仓库；价格依次为：9, 7, 2, 8, 14, 1, 8
• 一共有 4 次查询，查询发生的时间分别是：
  • 前 1、前 2、前 6、前 6 件货物进入后
• 注意：第 $j$ 次查询，不是问“第几件货物”，而是问：当前已有的这些货物里，按价格从小到大排，第 $j$ 位是多少。
• 第 1 次查询（$B[j] = 1$）：
  • 此时前 1 件货物 = [9]，排序后 [9]。
  • 第 1 次查找第 1 位，答案：9。
• 第 2 次查询（$B[j] = 2$）：
  • 此时前 2 件货物 = [9, 7]，排序后得到：[7, 9]。
  • 第 2 次查询要找第 2 位，答案：9。
• 第 3 次查询（$B[j] = 6$）：
  • 此时前 6 件货物 = [9, 7, 2, 8, 14, 1]，排序后得到：[1, 2, 7, 8, 9, 14]。
  • 第 3 次查询要找第 3 位，答案：7。
• 第 4 次查询（$B[j] = 6$）：
  • 此时前 6 件货物 = [9, 7, 2, 8, 14, 1]，排序后得到：[1, 2, 7, 8, 9, 14]。
  • 第 4 次查询要找第 4 位，答案：8。

样例2

输入

5,5,[8,4,4,10,9],[1,2,3,5,5]

输出

[8,8,8,9,10]

说明

• 一共有 5 件货物，价格依次为：8, 4, 4, 10, 9
• 一共有 5 次查询，发生时机分别是：
  • 前 1、前 2、前 3、前 5、前 5 件货物进入之后
• 第 1 次查询（$B[j] = 1$）：
  • 此时前 1 件货物 = [8]，排序后 [8]。
  • 找第 1 位，答案：8。
• 第 2 次查询（$B[j] = 2$）：
  • 此时前 2 件货物 = [8, 4]，排序后 [4, 8]。
  • 找第 2 位，答案：8。
• 第 3 次查询（$B[j] = 3$）：
  • 此时前 3 件货物 = [8, 4, 4]，排序后 [4, 4, 8]。
  • 找第 3 位，答案：8。
• 第 4 次查询（$B[j] = 5$）：
  • 此时前 5 件货物全部进入 = [8, 4, 4, 10, 9]，排序后 [4, 4, 8, 9, 10]。
  • 找第 4 位，答案：9。
• 第 5 次查询（$B[j] = 5$，与第 4 次查询时机相同）：
  • 此时还是前 5 件货物 = [4, 4, 8, 9, 10]。
  • 找第 5 位，答案：10。