这是问题的简单版本。在此版本中 $$$1 \le n, m \le 100$$$。只有解决并锁定这两个问题,你才能解决这个问题。
给定一个整数序列 $$$a=[a_1,a_2,\dots,a_n]$$$,长度为 $$$n$$$。它的子序列是通过从序列 $$$a$$$ 中删除零个或多个元素而获得的(它们不一定是连续的)。例如,对于序列 $$$a=[11,20,11,33,11,20,11]$$$:
- $$$[11,20,11,33,11,20,11]$$$, $$$[11,20,11,33,11,20]$$$, $$$[11,11,11,11]$$$, $$$[20]$$$, $$$[33,20]$$$ 是子序列(这些只是长列表中的一部分);
- $$$[40]$$$、$$$[33,33]$$$、$$$[33,20,20]$$$、$$$[20,20,11,11]$$$ 不是子序列。
假设给出一个额外的非负整数 $$$k$$$ ($$$1 \le k \le n$$$),则该子序列被称为最优,如果:
- 它的长度为$$$k$$$,其元素之和是长度为$$$k$$$的所有子序列中可能的最大值;
- 在满足前一项的长度 $$$k$$$ 的所有子序列中,它按字典顺序是最小的。
回想一下,序列 $$$b=[b_1, b_2, \dots, b_k]$$$ 按字典顺序小于序列 $$$c=[c_1, c_2, \dots, c_k]$$$,如果它们在序列 $$$b$$$ 中的差异小于 $$$c$$$ 中的差异较小的第一个元素(从左开始)。形式上:存在 $$$t$$$ ($$$1 \le t \le k$$$) 使得 $$$b_1=c_1$$$, $$$b_2=c_2$$$, ..., $$$b_{t-1}=c_{t-1}$$$ 并且同时 $$$b_t<c_t$$$。例如:
- $$$[10, 20, 20]$$$ 按字典顺序小于 $$$[10, 21, 1]$$$,
- $$$[7, 99, 99]$$$ 按字典顺序小于 $$$[10, 21, 1]$$$,
- $$$[10, 21, 0]$$$ 按字典顺序小于 $$$[10, 21, 1]$$$。
您将获得一系列 $$$a=[a_1,a_2,\dots,a_n]$$$ 和 $$$m$$$ 请求,每个请求包含两个数字 $$$k_j$$$ 和 $$$pos_j$$$ ($$$1 \le k \le n$$$, $$$1 \le pos_j \le k_j$$$)。对于每个查询,打印 $$$k=k_j$$$ 的给定序列 $$$a$$$ 的最佳子序列的索引 $$$pos_j$$$ 中的值。
例如,如果 $$$n=4$$$、$$$a=[10,20,30,20]$$$、$$$k_j=2$$$,则最佳子序列为 $$$[20,30]$$$ — 按字典顺序,它是所有长度为 $$$2$$$、项目总和最大的子序列中的最小子序列。因此,请求 $$$k_j=2$$$、$$$pos_j=1$$$ 的答案是数字 $$$20$$$,请求 $$$k_j=2$$$、$$$pos_j=2$$$ 的答案是数字 $$$30$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 序列 $$$a$$$ 的长度。
第二行包含序列 $$$a$$$ 的元素:整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 100$$$) — 请求数。
以下 $$$m$$$ 行包含整数对 $$$k_j$$$ 和 $$$pos_j$$$ ($$$1 \le k \le n$$$, $$$1 \le pos_j \le k_j$$$) — 请求。
输出
每行打印 $$$m$$$ 整数 $$$r_1, r_2, \dots, r_m$$$ ($$$1 \le r_j \le 10^9$$$):按照请求在输入中出现的顺序回答请求。 $$$r_j$$$ 的值应等于 $$$k=k_j$$$ 的最优子序列的位置 $$$pos_j$$$ 中包含的值。
示例
输入 #1
3 10 20 10 6 1 1 2 1 2 2 3 1 3 2 3 3
输出 #1
20 10 20 10 20 10
输入 #2
7 1 2 1 3 1 2 1 9 2 1 2 2 3 1 3 2 3 3 1 1 7 1 7 7 7 4
输出 #2
2 3 2 3 2 3 1 1 3
注意
在第一个示例中,对于 $$$a=[10,20,10]$$$ ,最佳子序列为:
- 对于 $$$k=1$$$: $$$[20]$$$,
- 对于 $$$k=2$$$: $$$[10,20]$$$,
- 对于 $$$k=3$$$:$$$[10,20,10]$$$。