#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool vmin(T& a, T b) {
  return (a > b) ? (a = b, true) : (false);
}
template <typename T>
bool vmax(T& a, T b) {
  return (a < b) ? (a = b, true) : (false);
}
template <typename T>
T smax(T x) {
  return x;
}
template <typename T, typename... K>
T smax(T a, const K&... args) {
  return max(a, smax(args...));
}
template <typename T>
T smin(T x) {
  return x;
}
template <typename T, typename... K>
T smin(T a, const K&... args) {
  return min(a, smin(args...));
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& z) {
  os << "(" << z.first << ", " << z.second << ')';
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
  bool isfirst = true;
  os << "{";
  for (auto z : a) {
    if (!isfirst) {
      os << ", ";
    }
    os << z;
    isfirst = false;
  }
  os << '}';
  return os;
}
const int inf = (signed)(~0u >> 2);
const long long llf = (signed long long)(~0ull >> 2);
template <typename T>
int vsize(vector<T>& x) {
  return (signed)x.size();
}
template <typename T>
void discrete(T* a, int* b, int n) {
  vector<T> v(a + 1, a + n + 1);
  sort(v.begin(), v.end());
  for (int i = 1; i <= n; i++)
    b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}
using namespace std;
namespace yyf {
template <typename T>
class Pool {
 protected:
  int sz;
  T* p;
  T* top;

 public:
  Pool(int sz = 0) : sz(sz) {
    p = new T[sz];
    top = p;
  }
  T* alloc() {
    if (top == p + sz) return new T();
    return top++;
  }
};
template <typename T>
class Treap {
 protected:
  typedef class Node {
   public:
    T v;
    int rd, sz;
    Node* fa;
    Node *l, *r;
    Node *pre, *suf;
    Node() : sz(1), fa(NULL), l(NULL), r(NULL), pre(NULL), suf(NULL) {}
    void push_up() {
      sz = 1;
      if (l) sz += l->sz;
      if (r) sz += r->sz;
    }
    int rank(int coef = 1) const {
      int x = ((l) ? (l->sz + 1) : (1)) * coef;
      if (fa) x += fa->rank(this == fa->r);
      return x;
    }
  } Node;
  Node* find_pre(Node* p) {
    if (!p) return p;
    if (p->l) {
      p = p->l;
      while (p->r) p = p->r;
      return p;
    }
    while (p->fa) {
      if (p->fa->r == p) return p->fa;
      p = p->fa;
    }
    return NULL;
  }
  Node* find_suf(Node* p) {
    if (!p) return p;
    if (p->r) {
      p = p->r;
      while (p->l) p = p->l;
      return p;
    }
    while (p->fa) {
      if (p->fa->l == p) return p->fa;
      p = p->fa;
    }
    return NULL;
  }
  void split_value(Node* p, const T& x, Node*& L, Node*& R) {
    if (!p) {
      L = R = NULL;
      return;
    }
    if (p->v <= x) {
      split_value(p->r, x, p->r, R);
      (p->r) ? (p->r->fa = p) : (0);
      L = p, p->push_up();
    } else {
      split_value(p->l, x, L, p->l);
      (p->l) ? (p->l->fa = p) : (0);
      R = p, p->push_up();
    }
  }
  pair<Node*, Node*> split_value(Node* p, const T& x) {
    pair<Node*, Node*> rt(NULL, NULL);
    split_value(p, x, rt.first, rt.second);
    return rt;
  }
  pair<Node*, Node*> split_rank(Node* p, int k) {
    if (!p) return pair<Node*, Node*>(NULL, NULL);
    p->fa = NULL;
    if (!k) return pair<Node*, Node*>(NULL, p);
    if (k >= p->sz) return pair<Node*, Node*>(p, NULL);
    pair<Node*, Node*> rt;
    int ls = ((p->l) ? (p->l->sz) : (0));
    if (ls < k) {
      rt = split_rank(p->r, k - ls - 1);
      if (rt.first) rt.first->fa = p;
      p->r = rt.first, rt.first = p;
      p->push_up();
      return rt;
    }
    rt = split_rank(p->l, k);
    if (rt.second) rt.second->fa = p;
    p->l = rt.second, rt.second = p;
    p->push_up();
    return rt;
  }
  Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->rd <= b->rd) {
      a->r = merge(a->r, b);
      a->push_up();
      if (a->r) a->r->fa = a;
      return a;
    }
    b->l = merge(a, b->l);
    b->push_up();
    if (b->l) b->l->fa = b;
    return b;
  }

 public:
  Pool<Node> pool;
  Node* alloc() {
    Node* p = pool.alloc();
    p->rd = ((unsigned int)rand()) << 15 ^ rand();
    return p;
  }
  typedef class Iterator {
   public:
    const Node* p;
    Iterator(const Node* p) : p(p) {}
    T operator*() { return p->v; }
    operator bool() { return p != NULL; }
    Iterator suf() { return p->suf; }
    Iterator pre() { return p->pre; }
    int rank() { return p->rank(); }
  } Iterator;
  Node* rt;
  Treap(int alloc_sz = 200000) : pool(alloc_sz) {}
  Iterator insert(const T& x) {
    Node* p = alloc();
    p->v = x;
    pair<Node*, Node*> par = split_value(rt, x);
    par.first = merge(par.first, p);
    rt = merge(par.first, par.second);
    p->pre = find_pre(p);
    p->suf = find_suf(p);
    if (p->pre) p->pre->suf = p;
    if (p->suf) p->suf->pre = p;
    return p;
  }
  void erase(const T& x) {
    pair<Node*, Node*> a = split_value(rt, x);
    assert(a.first);
    pair<Node*, Node*> b = split_rank(a.first, a.first->sz - 1);
    assert(b.second);
    Node* p = b.second;
    if (p->pre) p->pre->suf = p->suf;
    if (p->suf) p->suf->pre = p->pre;
    rt = merge(b.first, a.second);
  }
  template <typename Tp>
  Iterator lower_bound(const Tp& x) {
    Node *p = rt, *q = NULL;
    while (p) {
      if (p->v < x) {
        p = p->r;
      } else {
        q = p, p = p->l;
      }
    }
    return q;
  }
  template <typename Tp>
  Iterator upper_bound(const Tp& x) {
    Node *p = rt, *q = NULL;
    while (p) {
      if (p->v <= x) {
        p = p->r;
      } else {
        q = p, p = p->l;
      }
    }
    return q;
  }
  Iterator find_by_rank(int k) {
    if (!rt || k <= 0 || k > rt->sz) return NULL;
    Node* p = rt;
    while (p) {
      int ls = ((p->l) ? (p->l->sz) : (0));
      if (k == ls + 1) {
        return p;
      }
      if (ls < k) {
        k -= ls + 1;
        p = p->r;
      } else {
        p = p->l;
      }
    }
    assert(false);
    return NULL;
  }
  template <typename Tp>
  int rank(const Tp& x) {
    if (!rt) return 0;
    Iterator p = lower_bound(x);
    if (!p) return rt->sz + 1;
    return p ? p.rank() : 0;
  }
  int size() { return (rt) ? (rt->sz) : (0); }
  template <typename Tp>
  Iterator find_pre(const Tp& x) {
    if (!rt) return rt;
    Iterator it = lower_bound(x);
    if (it) {
      return it.pre();
    }
    Node* p = rt;
    while (p->r) p = p->r;
    return p;
  }
};
}  // namespace yyf
using namespace yyf;
const int N = 2e5 + 5;
int n, m;
int a[N];
int ans[N];
vector<pair<int, int> > b;
Treap<int> tr;
vector<pair<int, int> > qry[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) b.emplace_back(-a[i], i);
  cin >> m;
  for (int i = 1, k, x; i <= m; i++) {
    cin >> k >> x;
    qry[k].emplace_back(x, i);
  }
  sort(b.begin(), b.end());
  for (int i = 1; i <= n; i++) {
    int p = b[i - 1].second;
    tr.insert(p);
    for (auto t : qry[i]) {
      int q = *tr.find_by_rank(t.first);
      ans[t.second] = a[q];
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

### Prompt

Please formulate 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;
template <typename T>
bool vmin(T& a, T b) {
  return (a > b) ? (a = b, true) : (false);
}
template <typename T>
bool vmax(T& a, T b) {
  return (a < b) ? (a = b, true) : (false);
}
template <typename T>
T smax(T x) {
  return x;
}
template <typename T, typename... K>
T smax(T a, const K&... args) {
  return max(a, smax(args...));
}
template <typename T>
T smin(T x) {
  return x;
}
template <typename T, typename... K>
T smin(T a, const K&... args) {
  return min(a, smin(args...));
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& z) {
  os << "(" << z.first << ", " << z.second << ')';
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
  bool isfirst = true;
  os << "{";
  for (auto z : a) {
    if (!isfirst) {
      os << ", ";
    }
    os << z;
    isfirst = false;
  }
  os << '}';
  return os;
}
const int inf = (signed)(~0u >> 2);
const long long llf = (signed long long)(~0ull >> 2);
template <typename T>
int vsize(vector<T>& x) {
  return (signed)x.size();
}
template <typename T>
void discrete(T* a, int* b, int n) {
  vector<T> v(a + 1, a + n + 1);
  sort(v.begin(), v.end());
  for (int i = 1; i <= n; i++)
    b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}
using namespace std;
namespace yyf {
template <typename T>
class Pool {
 protected:
  int sz;
  T* p;
  T* top;

 public:
  Pool(int sz = 0) : sz(sz) {
    p = new T[sz];
    top = p;
  }
  T* alloc() {
    if (top == p + sz) return new T();
    return top++;
  }
};
template <typename T>
class Treap {
 protected:
  typedef class Node {
   public:
    T v;
    int rd, sz;
    Node* fa;
    Node *l, *r;
    Node *pre, *suf;
    Node() : sz(1), fa(NULL), l(NULL), r(NULL), pre(NULL), suf(NULL) {}
    void push_up() {
      sz = 1;
      if (l) sz += l->sz;
      if (r) sz += r->sz;
    }
    int rank(int coef = 1) const {
      int x = ((l) ? (l->sz + 1) : (1)) * coef;
      if (fa) x += fa->rank(this == fa->r);
      return x;
    }
  } Node;
  Node* find_pre(Node* p) {
    if (!p) return p;
    if (p->l) {
      p = p->l;
      while (p->r) p = p->r;
      return p;
    }
    while (p->fa) {
      if (p->fa->r == p) return p->fa;
      p = p->fa;
    }
    return NULL;
  }
  Node* find_suf(Node* p) {
    if (!p) return p;
    if (p->r) {
      p = p->r;
      while (p->l) p = p->l;
      return p;
    }
    while (p->fa) {
      if (p->fa->l == p) return p->fa;
      p = p->fa;
    }
    return NULL;
  }
  void split_value(Node* p, const T& x, Node*& L, Node*& R) {
    if (!p) {
      L = R = NULL;
      return;
    }
    if (p->v <= x) {
      split_value(p->r, x, p->r, R);
      (p->r) ? (p->r->fa = p) : (0);
      L = p, p->push_up();
    } else {
      split_value(p->l, x, L, p->l);
      (p->l) ? (p->l->fa = p) : (0);
      R = p, p->push_up();
    }
  }
  pair<Node*, Node*> split_value(Node* p, const T& x) {
    pair<Node*, Node*> rt(NULL, NULL);
    split_value(p, x, rt.first, rt.second);
    return rt;
  }
  pair<Node*, Node*> split_rank(Node* p, int k) {
    if (!p) return pair<Node*, Node*>(NULL, NULL);
    p->fa = NULL;
    if (!k) return pair<Node*, Node*>(NULL, p);
    if (k >= p->sz) return pair<Node*, Node*>(p, NULL);
    pair<Node*, Node*> rt;
    int ls = ((p->l) ? (p->l->sz) : (0));
    if (ls < k) {
      rt = split_rank(p->r, k - ls - 1);
      if (rt.first) rt.first->fa = p;
      p->r = rt.first, rt.first = p;
      p->push_up();
      return rt;
    }
    rt = split_rank(p->l, k);
    if (rt.second) rt.second->fa = p;
    p->l = rt.second, rt.second = p;
    p->push_up();
    return rt;
  }
  Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->rd <= b->rd) {
      a->r = merge(a->r, b);
      a->push_up();
      if (a->r) a->r->fa = a;
      return a;
    }
    b->l = merge(a, b->l);
    b->push_up();
    if (b->l) b->l->fa = b;
    return b;
  }

 public:
  Pool<Node> pool;
  Node* alloc() {
    Node* p = pool.alloc();
    p->rd = ((unsigned int)rand()) << 15 ^ rand();
    return p;
  }
  typedef class Iterator {
   public:
    const Node* p;
    Iterator(const Node* p) : p(p) {}
    T operator*() { return p->v; }
    operator bool() { return p != NULL; }
    Iterator suf() { return p->suf; }
    Iterator pre() { return p->pre; }
    int rank() { return p->rank(); }
  } Iterator;
  Node* rt;
  Treap(int alloc_sz = 200000) : pool(alloc_sz) {}
  Iterator insert(const T& x) {
    Node* p = alloc();
    p->v = x;
    pair<Node*, Node*> par = split_value(rt, x);
    par.first = merge(par.first, p);
    rt = merge(par.first, par.second);
    p->pre = find_pre(p);
    p->suf = find_suf(p);
    if (p->pre) p->pre->suf = p;
    if (p->suf) p->suf->pre = p;
    return p;
  }
  void erase(const T& x) {
    pair<Node*, Node*> a = split_value(rt, x);
    assert(a.first);
    pair<Node*, Node*> b = split_rank(a.first, a.first->sz - 1);
    assert(b.second);
    Node* p = b.second;
    if (p->pre) p->pre->suf = p->suf;
    if (p->suf) p->suf->pre = p->pre;
    rt = merge(b.first, a.second);
  }
  template <typename Tp>
  Iterator lower_bound(const Tp& x) {
    Node *p = rt, *q = NULL;
    while (p) {
      if (p->v < x) {
        p = p->r;
      } else {
        q = p, p = p->l;
      }
    }
    return q;
  }
  template <typename Tp>
  Iterator upper_bound(const Tp& x) {
    Node *p = rt, *q = NULL;
    while (p) {
      if (p->v <= x) {
        p = p->r;
      } else {
        q = p, p = p->l;
      }
    }
    return q;
  }
  Iterator find_by_rank(int k) {
    if (!rt || k <= 0 || k > rt->sz) return NULL;
    Node* p = rt;
    while (p) {
      int ls = ((p->l) ? (p->l->sz) : (0));
      if (k == ls + 1) {
        return p;
      }
      if (ls < k) {
        k -= ls + 1;
        p = p->r;
      } else {
        p = p->l;
      }
    }
    assert(false);
    return NULL;
  }
  template <typename Tp>
  int rank(const Tp& x) {
    if (!rt) return 0;
    Iterator p = lower_bound(x);
    if (!p) return rt->sz + 1;
    return p ? p.rank() : 0;
  }
  int size() { return (rt) ? (rt->sz) : (0); }
  template <typename Tp>
  Iterator find_pre(const Tp& x) {
    if (!rt) return rt;
    Iterator it = lower_bound(x);
    if (it) {
      return it.pre();
    }
    Node* p = rt;
    while (p->r) p = p->r;
    return p;
  }
};
}  // namespace yyf
using namespace yyf;
const int N = 2e5 + 5;
int n, m;
int a[N];
int ans[N];
vector<pair<int, int> > b;
Treap<int> tr;
vector<pair<int, int> > qry[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) b.emplace_back(-a[i], i);
  cin >> m;
  for (int i = 1, k, x; i <= m; i++) {
    cin >> k >> x;
    qry[k].emplace_back(x, i);
  }
  sort(b.begin(), b.end());
  for (int i = 1; i <= n; i++) {
    int p = b[i - 1].second;
    tr.insert(p);
    for (auto t : qry[i]) {
      int q = *tr.find_by_rank(t.first);
      ans[t.second] = a[q];
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

```