#include <bits/stdc++.h>
const int LG = 21;
const int N = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;
using namespace std;
int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No", "Yes"};
string YES[2] = {"NO", "YES"};
long long inq(long long x, long long y) {
  if (!y) return 1 % MOD;
  long long l = inq(x, y / 2);
  if (y % 2) return l * l % MOD * x % MOD;
  return l * l % MOD;
}
long long rev(long long x) { return inq(x, MOD - 2); }
bool __precomputed_combinatorics = 0;
vector<long long> __fact, __ufact, __rev;
void __precompute_combinatorics() {
  __precomputed_combinatorics = 1;
  __fact.resize(N);
  __ufact.resize(N);
  __rev.resize(N);
  __rev[1] = 1;
  for (int i = 2; i < N; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
  __fact[0] = 1, __ufact[0] = 1;
  for (int i = 1; i < N; i++)
    __fact[i] = __fact[i - 1] * i % MOD,
    __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}
long long fact(int x) {
  if (!__precomputed_combinatorics) __precompute_combinatorics();
  return __fact[x];
}
long long cnk(int n, int k) {
  if (k < 0 || k > n) return 0;
  if (!__precomputed_combinatorics) __precompute_combinatorics();
  return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}
int Root(int x, vector<int> &root) {
  if (x == root[x]) return x;
  return root[x] = Root(root[x], root);
}
void Merge(int v, int u, vector<int> &root, vector<int> &sz) {
  v = Root(v, root), u = Root(u, root);
  if (v == u) return;
  if (sz[v] < sz[u]) {
    sz[u] += sz[v];
    root[v] = u;
  } else {
    sz[v] += sz[u];
    root[u] = v;
  }
}
int ok(int x, int n) { return 0 <= x && x < n; }
void bfs(int v, vector<int> &dist, vector<vector<int> > &graph) {
  fill((dist).begin(), (dist).end(), -1);
  dist[v] = 0;
  vector<int> q = {v};
  for (int i = 0; i < q.size(); i++) {
    for (auto u : graph[q[i]]) {
      if (dist[u] == -1) {
        dist[u] = dist[q[i]] + 1;
        q.push_back(u);
      }
    }
  }
}
vector<int> z_func(string &s) {
  vector<int> z(s.size());
  z[0] = s.size();
  int L = 0, R = 0;
  for (int i = 1; i < s.size(); i++) {
    z[i] = max(0, min(z[i - L], R - i));
    while (i + z[i] < s.size() && s[i + z[i]] == s[z[i]]) z[i]++;
    if (i + z[i] > R) {
      R = i + z[i];
      L = i;
    }
  }
  return z;
}
vector<int> p_func(string &s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); i++) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) j++;
    p[i] = j;
  }
  return p;
}
vector<int> d1_func(string &s) {
  vector<int> d1(s.size());
  int L = 0, R = -1;
  for (int i = 0; i < s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d1[R - i + L]);
    while (i + k < s.size() && i - k >= 0 && s[i - k] == s[i + k]) k++;
    d1[i] = k--;
    if (i + k > R) {
      L = i - k;
      R = i + k;
    }
  }
  return d1;
}
vector<int> d2_func(string &s) {
  vector<int> d2(s.size());
  int L = 0, R = -1;
  for (int i = 1; i < s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d2[R - i + L + 1]);
    while (i + k < s.size() && i - k - 1 >= 0 && s[i - k - 1] == s[i + k]) k++;
    d2[i] = k--;
    if (i + k > R) {
      L = i - k - 1;
      R = i + k;
    }
  }
  return d2;
}
long long log10(long long x) {
  if (x < 10) return 1;
  return 1 + log10(x / 10);
}
long long ds(long long x) {
  if (x < 10) return x;
  return x % 10 + ds(x / 10);
}
double sqr(double x) { return x * x; }
bool in(int bit, int mask) { return (mask & (1 << bit)) > 0; }
void Del(vector<int> &v, int pos) {
  swap(v[pos], v[v.size() - 1]);
  v.pop_back();
}
long long g(vector<long long> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int g(vector<int> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int n, q;
int a[N];
pair<int, int> s[N];
struct qu {
  int len, pos, id;
};
int ans[N];
qu ask[N];
bool comp(qu a, qu b) { return a.len < b.len; }
int tree[4 * N];
void On(int pos, int L = 0, int R = n, int V = 0) {
  if (L + 1 == R) {
    tree[V] = 1;
    return;
  }
  int M = (L + R) / 2;
  if (pos < M)
    On(pos, L, M, 2 * V + 1);
  else
    On(pos, M, R, 2 * V + 2);
  tree[V] = tree[2 * V + 1] + tree[2 * V + 2];
}
int Find(int pos, int L = 0, int R = n, int V = 0) {
  if (L + 1 == R) {
    return L;
  }
  int M = (L + R) / 2;
  if (tree[2 * V + 1] > pos) {
    return Find(pos, L, M, 2 * V + 1);
  } else {
    pos -= tree[2 * V + 1];
    return Find(pos, M, R, 2 * V + 2);
  }
}
signed main() {
  srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int(i) = 0; (i) != (n); (i)++) {
    cin >> a[i];
    s[i] = {a[i], -i};
  }
  sort(s, s + n);
  reverse(s, s + n);
  for (int(i) = 0; (i) != (n); (i)++) {
    s[i].second *= -1;
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> ask[i].len >> ask[i].pos;
    ask[i].id = i;
  }
  sort(ask, ask + q, comp);
  int curlen = 0;
  for (int i = 0; i < q; i++) {
    while (curlen < ask[i].len) {
      On(s[curlen].second);
      curlen++;
    }
    ans[ask[i].id] = Find(ask[i].pos - 1);
  }
  for (int(i) = 0; (i) != (q); (i)++) {
    cout << a[ans[i]] << "\n";
  }
}

### Prompt

Create a solution in Cpp for the following problem:

This is the harder version of the problem. In this version, 1 ≤ n, m ≤ 2⋅10^5. You can hack this problem if you locked it. But you can hack the previous problem only if you locked 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 ≤ 2⋅10^5) — 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 ≤ 2⋅10^5) — 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>
const int LG = 21;
const int N = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;
using namespace std;
int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No", "Yes"};
string YES[2] = {"NO", "YES"};
long long inq(long long x, long long y) {
  if (!y) return 1 % MOD;
  long long l = inq(x, y / 2);
  if (y % 2) return l * l % MOD * x % MOD;
  return l * l % MOD;
}
long long rev(long long x) { return inq(x, MOD - 2); }
bool __precomputed_combinatorics = 0;
vector<long long> __fact, __ufact, __rev;
void __precompute_combinatorics() {
  __precomputed_combinatorics = 1;
  __fact.resize(N);
  __ufact.resize(N);
  __rev.resize(N);
  __rev[1] = 1;
  for (int i = 2; i < N; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
  __fact[0] = 1, __ufact[0] = 1;
  for (int i = 1; i < N; i++)
    __fact[i] = __fact[i - 1] * i % MOD,
    __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}
long long fact(int x) {
  if (!__precomputed_combinatorics) __precompute_combinatorics();
  return __fact[x];
}
long long cnk(int n, int k) {
  if (k < 0 || k > n) return 0;
  if (!__precomputed_combinatorics) __precompute_combinatorics();
  return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}
int Root(int x, vector<int> &root) {
  if (x == root[x]) return x;
  return root[x] = Root(root[x], root);
}
void Merge(int v, int u, vector<int> &root, vector<int> &sz) {
  v = Root(v, root), u = Root(u, root);
  if (v == u) return;
  if (sz[v] < sz[u]) {
    sz[u] += sz[v];
    root[v] = u;
  } else {
    sz[v] += sz[u];
    root[u] = v;
  }
}
int ok(int x, int n) { return 0 <= x && x < n; }
void bfs(int v, vector<int> &dist, vector<vector<int> > &graph) {
  fill((dist).begin(), (dist).end(), -1);
  dist[v] = 0;
  vector<int> q = {v};
  for (int i = 0; i < q.size(); i++) {
    for (auto u : graph[q[i]]) {
      if (dist[u] == -1) {
        dist[u] = dist[q[i]] + 1;
        q.push_back(u);
      }
    }
  }
}
vector<int> z_func(string &s) {
  vector<int> z(s.size());
  z[0] = s.size();
  int L = 0, R = 0;
  for (int i = 1; i < s.size(); i++) {
    z[i] = max(0, min(z[i - L], R - i));
    while (i + z[i] < s.size() && s[i + z[i]] == s[z[i]]) z[i]++;
    if (i + z[i] > R) {
      R = i + z[i];
      L = i;
    }
  }
  return z;
}
vector<int> p_func(string &s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); i++) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) j++;
    p[i] = j;
  }
  return p;
}
vector<int> d1_func(string &s) {
  vector<int> d1(s.size());
  int L = 0, R = -1;
  for (int i = 0; i < s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d1[R - i + L]);
    while (i + k < s.size() && i - k >= 0 && s[i - k] == s[i + k]) k++;
    d1[i] = k--;
    if (i + k > R) {
      L = i - k;
      R = i + k;
    }
  }
  return d1;
}
vector<int> d2_func(string &s) {
  vector<int> d2(s.size());
  int L = 0, R = -1;
  for (int i = 1; i < s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d2[R - i + L + 1]);
    while (i + k < s.size() && i - k - 1 >= 0 && s[i - k - 1] == s[i + k]) k++;
    d2[i] = k--;
    if (i + k > R) {
      L = i - k - 1;
      R = i + k;
    }
  }
  return d2;
}
long long log10(long long x) {
  if (x < 10) return 1;
  return 1 + log10(x / 10);
}
long long ds(long long x) {
  if (x < 10) return x;
  return x % 10 + ds(x / 10);
}
double sqr(double x) { return x * x; }
bool in(int bit, int mask) { return (mask & (1 << bit)) > 0; }
void Del(vector<int> &v, int pos) {
  swap(v[pos], v[v.size() - 1]);
  v.pop_back();
}
long long g(vector<long long> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int g(vector<int> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int n, q;
int a[N];
pair<int, int> s[N];
struct qu {
  int len, pos, id;
};
int ans[N];
qu ask[N];
bool comp(qu a, qu b) { return a.len < b.len; }
int tree[4 * N];
void On(int pos, int L = 0, int R = n, int V = 0) {
  if (L + 1 == R) {
    tree[V] = 1;
    return;
  }
  int M = (L + R) / 2;
  if (pos < M)
    On(pos, L, M, 2 * V + 1);
  else
    On(pos, M, R, 2 * V + 2);
  tree[V] = tree[2 * V + 1] + tree[2 * V + 2];
}
int Find(int pos, int L = 0, int R = n, int V = 0) {
  if (L + 1 == R) {
    return L;
  }
  int M = (L + R) / 2;
  if (tree[2 * V + 1] > pos) {
    return Find(pos, L, M, 2 * V + 1);
  } else {
    pos -= tree[2 * V + 1];
    return Find(pos, M, R, 2 * V + 2);
  }
}
signed main() {
  srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int(i) = 0; (i) != (n); (i)++) {
    cin >> a[i];
    s[i] = {a[i], -i};
  }
  sort(s, s + n);
  reverse(s, s + n);
  for (int(i) = 0; (i) != (n); (i)++) {
    s[i].second *= -1;
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> ask[i].len >> ask[i].pos;
    ask[i].id = i;
  }
  sort(ask, ask + q, comp);
  int curlen = 0;
  for (int i = 0; i < q; i++) {
    while (curlen < ask[i].len) {
      On(s[curlen].second);
      curlen++;
    }
    ans[ask[i].id] = Find(ask[i].pos - 1);
  }
  for (int(i) = 0; (i) != (q); (i)++) {
    cout << a[ans[i]] << "\n";
  }
}

```