1227_D1. Optimal Subsequences (Easy Version)
This is the easier version of the problem. In this version 1 ≤ n, m ≤ 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,...,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 ≤ k ≤ 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, ..., b_k] is lexicographically smaller than the sequence c=[c_1, c_2, ..., 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 ≤ t ≤ 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,...,a_n] and m requests, each consisting of two numbers k_j and pos_j (1 ≤ k ≤ n, 1 ≤ pos_j ≤ 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 ≤ n ≤ 100) — the length of the sequence a.

The second line contains elements of the sequence a: integer numbers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

The third line contains an integer m (1 ≤ m ≤ 100) — the number of requests.

The following m lines contain pairs of integers k_j and pos_j (1 ≤ k ≤ n, 1 ≤ pos_j ≤ k_j) — the requests.

Output

Print m integers r_1, r_2, ..., r_m (1 ≤ r_j ≤ 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.

Examples

Input


3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3


Output


20
10
20
10
20
10


Input


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


Output


2
3
2
3
2
3
1
1
3

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]. 
```python
# class SegmentTree(): # adapted from https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
#     def __init__(self,arr,func,initialRes=0):
#         self.f=func
#         self.N=len(arr) 
#         self.tree=[0 for _ in range(2*self.N)]
#         self.initialRes=initialRes
#         for i in range(self.N):
#             self.tree[self.N+i]=arr[i]
#         for i in range(self.N-1,0,-1):
#             self.tree[i]=self.f(self.tree[i<<1],self.tree[i<<1|1])
#     def updateTreeNode(self,idx,value): #update value at arr[idx]
#         self.tree[idx+self.N]=value
#         idx+=self.N
#         i=idx
#         while i>1:
#             self.tree[i>>1]=self.f(self.tree[i],self.tree[i^1])
#             i>>=1
#     def query(self,l,r): #get sum (or whatever function) on interval [l,r] inclusive
#         r+=1
#         res=self.initialRes
#         l+=self.N
#         r+=self.N
#         while l<r:
#             if l&1:
#                 res=self.f(res,self.tree[l])
#                 l+=1
#             if r&1:
#                 r-=1
#                 res=self.f(res,self.tree[r])
#             l>>=1
#             r>>=1
#         return res
# def getMaxSegTree(arr):
#     return SegmentTree(arr,lambda a,b:max(a,b),initialRes=-float('inf'))
# def getMinSegTree(arr):
#     return SegmentTree(arr,lambda a,b:min(a,b),initialRes=float('inf'))
# def getSumSegTree(arr):
#     return SegmentTree(arr,lambda a,b:a+b,initialRes=0)
from collections import Counter
def main():
    
    # mlogn solution
    n=int(input())
    a=readIntArr()
    
    b=sorted(a,reverse=True)
    
    m=int(input())
    allans=[]
    for _ in range(m):
        k,pos=readIntArr()
        cnt=Counter(b[:k])
        totalCnts=0
        for x in a:
            if cnt[x]>0:
                cnt[x]-=1
                totalCnts+=1
                if totalCnts==pos:
                    allans.append(x)
                    break
    multiLineArrayPrint(allans)
    
    return

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.
 
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]

def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(i,j):
    print('? {} {}'.format(i,j))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
 
inf=float('inf')
MOD=10**9+7
# MOD=998244353
 
 
for _abc in range(1):
    main()
```