#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long INF = (long long)5e18;
const int MOD = 998244353;
int add(int x, int y) {
  x += y;
  return x >= MOD ? x - MOD : x;
}
int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + MOD : x;
}
void Add(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
void Sub(int &x, int y) {
  x -= y;
  if (x < 0) x += MOD;
}
void Mul(int &x, int y) { x = (long long)(x) * (y) % MOD; }
int qpow(int x, int y) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = (long long)(ret) * (x) % MOD;
    x = (long long)(x) * (x) % MOD;
    y >>= 1;
  }
  return ret;
}
void checkmin(int &x, int y) {
  if (x > y) x = y;
}
void checkmax(int &x, int y) {
  if (x < y) x = y;
}
void checkmin(long long &x, long long y) {
  if (x > y) x = y;
}
void checkmax(long long &x, long long y) {
  if (x < y) x = y;
}
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return x * f;
}
const int N = 200005;
int n, a[N], val[N], m, nn;
vector<int> v[N];
struct node {
  int k, pos, id;
  bool operator<(const node &rhs) const { return k < rhs.k; }
} Q[N];
namespace BIT {
int a[N];
int lowbit(int x) { return x & (-x); }
void update(int x) {
  for (int i = x; i <= n; i += lowbit(i)) a[i]++;
}
int query(int x) {
  int ret = 0;
  for (int i = x; i; i -= lowbit(i)) ret += a[i];
  return ret;
}
}  // namespace BIT
vector<int> G[N];
int ans[N];
void init() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), val[i] = a[i];
  sort(val + 1, val + n + 1);
  nn = unique(val + 1, val + n + 1) - val - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(val + 1, val + nn + 1, a[i]) - val;
  for (int i = n; i >= 1; i--) v[a[i]].push_back(i);
  m = read();
  for (int i = 1; i <= m; i++) {
    Q[i].k = read(), Q[i].pos = read(), Q[i].id = i;
    G[Q[i].k].push_back(i);
  }
}
int find(int x) {
  int l = 0, r = n, mid, best;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (BIT::query(mid) >= x)
      best = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return best;
}
void solve() {
  int now = n;
  for (int i = 1; i <= n; i++) {
    while (v[now].empty() && now >= 1) now--;
    int pos = v[now].back();
    v[now].pop_back();
    BIT::update(pos);
    for (auto &to : G[i]) {
      node u = Q[to];
      ans[u.id] = find(u.pos);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", val[a[ans[i]]]);
}
int main() {
  init();
  solve();
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long INF = (long long)5e18;
const int MOD = 998244353;
int add(int x, int y) {
  x += y;
  return x >= MOD ? x - MOD : x;
}
int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + MOD : x;
}
void Add(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
void Sub(int &x, int y) {
  x -= y;
  if (x < 0) x += MOD;
}
void Mul(int &x, int y) { x = (long long)(x) * (y) % MOD; }
int qpow(int x, int y) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = (long long)(ret) * (x) % MOD;
    x = (long long)(x) * (x) % MOD;
    y >>= 1;
  }
  return ret;
}
void checkmin(int &x, int y) {
  if (x > y) x = y;
}
void checkmax(int &x, int y) {
  if (x < y) x = y;
}
void checkmin(long long &x, long long y) {
  if (x > y) x = y;
}
void checkmax(long long &x, long long y) {
  if (x < y) x = y;
}
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return x * f;
}
const int N = 200005;
int n, a[N], val[N], m, nn;
vector<int> v[N];
struct node {
  int k, pos, id;
  bool operator<(const node &rhs) const { return k < rhs.k; }
} Q[N];
namespace BIT {
int a[N];
int lowbit(int x) { return x & (-x); }
void update(int x) {
  for (int i = x; i <= n; i += lowbit(i)) a[i]++;
}
int query(int x) {
  int ret = 0;
  for (int i = x; i; i -= lowbit(i)) ret += a[i];
  return ret;
}
}  // namespace BIT
vector<int> G[N];
int ans[N];
void init() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), val[i] = a[i];
  sort(val + 1, val + n + 1);
  nn = unique(val + 1, val + n + 1) - val - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(val + 1, val + nn + 1, a[i]) - val;
  for (int i = n; i >= 1; i--) v[a[i]].push_back(i);
  m = read();
  for (int i = 1; i <= m; i++) {
    Q[i].k = read(), Q[i].pos = read(), Q[i].id = i;
    G[Q[i].k].push_back(i);
  }
}
int find(int x) {
  int l = 0, r = n, mid, best;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (BIT::query(mid) >= x)
      best = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return best;
}
void solve() {
  int now = n;
  for (int i = 1; i <= n; i++) {
    while (v[now].empty() && now >= 1) now--;
    int pos = v[now].back();
    v[now].pop_back();
    BIT::update(pos);
    for (auto &to : G[i]) {
      node u = Q[to];
      ans[u.id] = find(u.pos);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", val[a[ans[i]]]);
}
int main() {
  init();
  solve();
  return 0;
}

```