#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 4e5 + 47, mod = 1e9 + 7, inf = 1e9 + 7;
long long n, m;
vector<long long> val;
void read() {
  cin >> n;
  val.resize(n);
  for (long long i = 0; i < n; ++i) cin >> val[i];
}
vector<long long> fenw(MAXN, 0);
void update(long long pos) {
  for (; pos < MAXN; pos = (pos | (pos + 1))) fenw[pos]++;
}
long long get_sum(long long l) {
  long long res = 0;
  for (; l >= 0; l = (l & (l + 1)) - 1) res += fenw[l];
  return res;
}
bool comp(pair<long long, long long> &a, pair<long long, long long> &b) {
  if (a.first < b.first) return false;
  if (a.first > b.first) return true;
  return a.second <= b.second;
}
void solve() {
  cin >> m;
  vector<vector<pair<long long, long long> > > quer(n + 1);
  for (long long i = 0; i < m; ++i) {
    long long x, y;
    cin >> x >> y;
    quer[x - 1].push_back({y, i});
  }
  vector<pair<long long, long long> > suck(n);
  for (long long i = 0; i < n; ++i) suck[i] = {val[i], i};
  sort(suck.begin(), suck.end(), comp);
  vector<long long> ans(m, 0);
  for (long long len = 0; len < n; ++len) {
    update(suck[len].second);
    for (pair<long long, long long> p : quer[len]) {
      long long k = p.first;
      long long l = 0, r = n;
      while (l < r) {
        long long mid = l + (r - l) / 2;
        if (get_sum(mid) < k)
          l = mid + 1;
        else
          r = mid;
      }
      ans[p.second] = val[l];
    }
  }
  for (long long i = 0; i < m; ++i) cout << ans[i] << " ";
  cout << endl;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t = 1;
  while (t--) {
    read();
    solve();
  }
}
