Optimal Subsequences (Easy Version) (Codeforces 1262D1)
Tags: Greedy, data structures

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$$$.

Input: 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.

Output: 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$$$.

Note: 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]$$$. 

Sample Inputs:
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3

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

Sample Outputs:
20
10
20
10
20
10

2
3
2
3
2
3
1
1
3

Solution (Python):
n = int(input())
arr = list(map(int, input().split(' ')))
ori = [i for i in arr]
arr = [(arr[i], i) for i in range(n)]
arr.sort(reverse=True, key=lambda x: (x[0], -1 * x[1]))
for _ in range(int(input())):
    ans = []
    [a, b] = list(map(int, input().split(' ')))
    for i in range(a):
        ans.append(arr[i][1])
    ans.sort()
    print(ori[ans[b - 1]])

Solution (Python):
def f(a, q):
    a = list(zip(a, range(len(a))))
    a.sort(key=lambda s: s[0], reverse=True)
    for i in range(q):
        (k, pos) = map(int, input().strip().split())
        res = a[:k]
        res.sort(key=lambda s: s[1])
        print(res[pos - 1][0])
a = input()
l = [*map(int, input().strip().split())]
q = int(input())
f(l, q)

Solution (Python):
def f(a, q):
    a = list(zip(a, range(len(a))))
    a.sort(key=lambda s: s[0], reverse=True)
    for i in range(q):
        (k, pos) = map(int, input().strip().split())
        res = a[:k]
        res.sort(key=lambda s: s[1])
        print(res[pos - 1][0])
a = input()
l = [*map(int, input().strip().split())]
q = int(input())
f(l, q)