#include <bits/stdc++.h>
using namespace std;
int n, h;
int t[400010], d[200005], a[200005], reva[200005], ans[200005];
map<int, vector<int>> amap;
pair<pair<int, int>, int> q[200005];
void apply(int p, int value) {
  if (p < n)
    d[p] += value;
  else
    t[p] += value;
}
void push(int p) {
  for (int s = h; s > 0; --s) {
    int i = p >> s;
    if (d[i] != 0) {
      apply(i << 1, d[i]);
      apply(i << 1 | 1, d[i]);
      d[i] = 0;
    }
  }
}
void inc(int l, int r, int value) {
  l += n, r += n;
  int l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) apply(l++, value);
    if (r & 1) apply(--r, value);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < 32; i++) {
    if ((n >> i) & 1) h = i + 1;
  }
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) amap[a[i]].push_back(i);
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    q[i].second = i;
    cin >> q[i].first.first >> q[i].first.second;
  }
  sort(q, q + m);
  int p = 0;
  for (auto mit = amap.rbegin(); mit != amap.rend(); mit++) {
    for (auto vit : (mit->second)) {
      reva[p++] = vit;
    }
  }
  int pos = 0;
  for (int i = 0; i < m; i++) {
    while (q[i].first.first > pos) {
      int val = reva[pos++];
      inc(val, n, 1);
    }
    int s = 0, e = n - 1, ansm = -1;
    while (s <= e) {
      int m = (s + e) / 2;
      push(n + m);
      if (t[n + m] >= q[i].first.second) {
        ansm = m;
        e = m - 1;
      } else
        s = m + 1;
    }
    ans[q[i].second] = a[ansm];
  }
  for (int i = 0; i < m; i++) cout << ans[i] << "\n";
  return 0;
}
