Optimal Subsequences (Easy Version)

题意翻译

**本题为较简单版本。** 给定一个长度为 $n$ 的正整数序列 $a_1,a_2,...,a_n$。 有 $m$ 个询问，每次询问给出两个正整数 $k,pos$。你需要找到一个长度为 $k$ 的**子序列**，且满足如下要求： - 该子序列的**元素和**是所有子序列中最大的； - 该子序列是所有满足上一条件的子序列中**字典序**最小的一个。 对于每个询问，输出该子序列的第 $pos$ 个元素的值。 $1 \le n,m \le 100$（这是与困难版本**唯一**的区别）， $\ 1 \le k \le n$，在同一询问中有 $1 \le pos \le k$。 Translated by HoshizoraZ

题目描述

This is the easier version of the problem. In this version $ 1 \le n, m \le 100 $ . You can hack this problem only if you solve and lock both problems. You are given a sequence of integers $ a=[a_1,a_2,\dots,a_n] $ of length $ n $ . Its subsequence is obtained by removing zero or more elements from the sequence $ a $ (they do not necessarily go consecutively). For example, for the sequence $ 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] $ are subsequences (these are just some of the long list); - $ [40] $ , $ [33,33] $ , $ [33,20,20] $ , $ [20,20,11,11] $ are not subsequences. Suppose that an additional non-negative integer $ k $ ( $ 1 \le k \le n $ ) is given, then the subsequence is called optimal if: - it has a length of $ k $ and the sum of its elements is the maximum possible among all subsequences of length $ k $ ; - and among all subsequences of length $ k $ that satisfy the previous item, it is lexicographically minimal. Recall that the sequence $ b=[b_1, b_2, \dots, b_k] $ is lexicographically smaller than the sequence $ c=[c_1, c_2, \dots, c_k] $ if the first element (from the left) in which they differ less in the sequence $ b $ than in $ c $ . Formally: there exists $ t $ ( $ 1 \le t \le k $ ) such that $ b_1=c_1 $ , $ b_2=c_2 $ , ..., $ b_{t-1}=c_{t-1} $ and at the same time $ b_t<c_t $ . For example: - $ [10, 20, 20] $ lexicographically less than $ [10, 21, 1] $ , - $ [7, 99, 99] $ is lexicographically less than $ [10, 21, 1] $ , - $ [10, 21, 0] $ is lexicographically less than $ [10, 21, 1] $ . You are given a sequence of $ a=[a_1,a_2,\dots,a_n] $ and $ m $ requests, each consisting of two numbers $ k_j $ and $ pos_j $ ( $ 1 \le k \le n $ , $ 1 \le pos_j \le k_j $ ). For each query, print the value that is in the index $ pos_j $ of the optimal subsequence of the given sequence $ a $ for $ k=k_j $ . For example, if $ n=4 $ , $ a=[10,20,30,20] $ , $ k_j=2 $ , then the optimal subsequence is $ [20,30] $ — it is the minimum lexicographically among all subsequences of length $ 2 $ with the maximum total sum of items. Thus, the answer to the request $ k_j=2 $ , $ pos_j=1 $ is the number $ 20 $ , and the answer to the request $ k_j=2 $ , $ pos_j=2 $ is the number $ 30 $ .

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1 \le n \le 100 $ ) — the length of the sequence $ a $ . The second line contains elements of the sequence $ a $ : integer numbers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ). The third line contains an integer $ m $ ( $ 1 \le m \le 100 $ ) — the number of requests. The following $ m $ lines contain pairs of integers $ k_j $ and $ pos_j $ ( $ 1 \le k \le n $ , $ 1 \le pos_j \le k_j $ ) — the requests.

输出格式

Print $ m $ integers $ r_1, r_2, \dots, r_m $ ( $ 1 \le r_j \le 10^9 $ ) one per line: answers to the requests in the order they appear in the input. The value of $ r_j $ should be equal to the value contained in the position $ pos_j $ of the optimal subsequence for $ k=k_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

说明

In the first example, for $ a=[10,20,10] $ the optimal subsequences are: - for $ k=1 $ : $ [20] $ , - for $ k=2 $ : $ [10,20] $ , - for $ k=3 $ : $ [10,20,10] $ .