CF1227D1 Optimal Subsequences (Easy Version)

这是该问题的简单版本。在本版本中 $1 \le n, m \le 100$。只有在你同时解决并锁定两个问题后，才能 hack 本题。 给定一个长度为 $n$ 的整数序列 $a=[a_1,a_2,\dots,a_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]$，当且仅当存在某个 $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_j \le n$，$1 \le pos_j \le k_j$）。对于每个询问，请输出对于 $k=k_j$ 时，最优子序列的第 $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_j \le n$，$1 \le pos_j \le k_j$），表示一次询问。

输出 $m$ 行，每行一个整数 $r_j$（$1 \le r_j \le 10^9$），依次为每个询问的答案。$r_j$ 应等于对于 $k=k_j$ 时，最优子序列的第 $pos_j$ 个位置上的值。

在第一个示例中，对于 $a=[10,20,10]$，最优子序列为： - 当 $k=1$ 时：$[20]$； - 当 $k=2$ 时：$[10,20]$； - 当 $k=3$ 时：$[10,20,10]$。 由 ChatGPT 4.1 翻译