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]. 
import java.io.BufferedReader;
// import java.io.FileInputStream;
// import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Random;
import java.util.StringTokenizer;

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.round;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;
import static java.util.Collections.reverseOrder;
import static java.util.Collections.sort;
import static java.util.Comparator.comparingInt;

public class Solution {
    FastScanner in;
    PrintWriter out;

    class Pair {
        int a, id;

        Pair(int a, int id) {
            this.a = a;
            this.id = id;
        }
    }

    class Triplet {
        int k, pos, id;

        Triplet(int k, int pos, int id) {
            this.k = k;
            this.pos = pos;
            this.id = id;
        }
    }

    private void solve() throws IOException {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();

        Pair[] p = new Pair[n];
        for (int i = 0; i < n; i++)
            p[i] = new Pair(a[i], i);
        sort(p, (o1, o2) -> o1.a != o2.a ? o2.a - o1.a : o1.id - o2.id);

        int m = in.nextInt();
        Triplet[] t = new Triplet[m];
        for (int i = 0; i < m; i++)
            t[i] = new Triplet(in.nextInt() - 1, in.nextInt() - 1, i);
        sort(t, comparingInt(o -> o.k));

        int[] ans = new int[m];
        AVLTreePBDS tree = new AVLTreePBDS(false);
        for (int i = 0, j = 0; i < n; i++) {
            tree.add(p[i].id);
            while (j < m && t[j].k == i) {
                ans[t[j].id] = a[tree.findByOrder(t[j].pos)];
                j++;
            }
        }

        for (int i = 0; i < m; i++)
            out.println(ans[i]);
    }

    class AVLTreePBDS {
        private Node root;
        private boolean multi;

        AVLTreePBDS(boolean multi) {
            this.root = null;
            this.multi = multi;
        }

        int size() {
            return size(root);
        }

        boolean isEmpty() {
            return size(root) == 0;
        }

        boolean contains(int key) {
            return contains(root, key);
        }

        void add(int key) {
            root = add(root, key);
        }

        void remove(int key) {
            root = remove(root, key);
        }

        Integer first() {
            Node min = findMin(root);
            return min != null ? min.key : null;
        }

        Integer last() {
            Node max = findMax(root);
            return max != null ? max.key : null;
        }

        Integer poolFirst() {
            Node min = findMin(root);
            if (min != null) {
                remove(min.key);
                return min.key;
            }
            return null;
        }

        Integer poolLast() {
            Node max = findMax(root);
            if (max != null) {
                remove(max.key);
                return max.key;
            }
            return null;
        }

        // min >= key
        Integer ceiling(int key) {
            return contains(key) ? key : higher(key);
        }

        // max <= key
        Integer floor(int key) {
            return contains(key) ? key : lower(key);
        }

        // min > key
        Integer higher(int key) {
            Node min = higher(root, key);
            return min == null ? null : min.key;
        }

        private Node higher(Node cur, int key) {
            if (cur == null)
                return null;

            if (cur.key <= key)
                return higher(cur.right, key);

            // cur.key > key
            Node left = higher(cur.left, key);
            return left == null ? cur : left;
        }

        // max < key
        Integer lower(int key) {
            Node max = lower(root, key);
            return max == null ? null : max.key;
        }

        private Node lower(Node cur, int key) {
            if (cur == null)
                return null;

            if (cur.key >= key)
                return lower(cur.left, key);

            // cur.key < key
            Node right = lower(cur.right, key);
            return right == null ? cur : right;
        }

        private class Node {
            int key, height, size;
            Node left, right;

            Node(int key) {
                this.key = key;
                height = size = 1;
                left = right = null;
            }
        }

        private int height(Node cur) {
            return cur == null ? 0 : cur.height;
        }

        private int balanceFactor(Node cur) {
            return height(cur.right) - height(cur.left);
        }

        private int size(Node cur) {
            return cur == null ? 0 : cur.size;
        }

        // fixVertex
        private void fixHeightAndSize(Node cur) {
            cur.height = max(height(cur.left), height(cur.right)) + 1;
            cur.size = size(cur.left) + size(cur.right) + 1;
        }

        private Node rotateRight(Node cur) {
            Node prevLeft = cur.left;
            cur.left = prevLeft.right;
            prevLeft.right = cur;
            fixHeightAndSize(cur);
            fixHeightAndSize(prevLeft);
            return prevLeft;
        }

        private Node rotateLeft(Node cur) {
            Node prevRight = cur.right;
            cur.right = prevRight.left;
            prevRight.left = cur;
            fixHeightAndSize(cur);
            fixHeightAndSize(prevRight);
            return prevRight;
        }

        private Node balance(Node cur) {
            fixHeightAndSize(cur);
            if (balanceFactor(cur) == 2) {
                if (balanceFactor(cur.right) < 0)
                    cur.right = rotateRight(cur.right);
                return rotateLeft(cur);
            }
            if (balanceFactor(cur) == -2) {
                if (balanceFactor(cur.left) > 0)
                    cur.left = rotateLeft(cur.left);
                return rotateRight(cur);
            }
            return cur;
        }

        private boolean contains(Node cur, int key) {
            if (cur == null)
                return false;
            else if (key < cur.key)
                return contains(cur.left, key);
            else if (key > cur.key)
                return contains(cur.right, key);
            else
                return true;
        }

        private Node add(Node cur, int key) {
            if (cur == null)
                return new Node(key);

            if (key < cur.key)
                cur.left = add(cur.left, key);
            else if (key > cur.key || multi)
                cur.right = add(cur.right, key);

            return balance(cur);
        }

        private Node findMin(Node cur) {
            return cur.left != null ? findMin(cur.left) : cur;
        }

        private Node findMax(Node cur) {
            return cur.right != null ? findMax(cur.right) : cur;
        }

        private Node removeMin(Node cur) {
            if (cur.left == null)
                return cur.right;

            cur.left = removeMin(cur.left);
            return balance(cur);
        }

        private Node removeMax(Node cur) {
            if (cur.right == null)
                return cur.left;

            cur.right = removeMax(cur.right);
            return balance(cur);
        }

        private Node remove(Node cur, int key) {
            if (cur == null)
                return null;

            if (key < cur.key)
                cur.left = remove(cur.left, key);
            else if (key > cur.key)
                cur.right = remove(cur.right, key);
            else { //  k == cur.key
                Node prevLeft = cur.left;
                Node prevRight = cur.right;

                if (prevRight == null)
                    return prevLeft;

                Node min = findMin(prevRight);
                min.right = removeMin(prevRight);
                min.left = prevLeft;

                return balance(min);
            }

            return balance(cur);
        }

        int orderOfKey(int key) {
            return orderOfKey(root, key);
        }

        // count < key
        private int orderOfKey(Node cur, int key) {
            if (cur == null)
                return 0;

            if (cur.key < key)
                return size(cur.left) + 1 + orderOfKey(cur.right, key);

            if (cur.key == key)
                return size(cur.left);

            // cur.key > key
            return orderOfKey(cur.left, key);
        }

        Integer findByOrder(int pos) {
            return size(root) > pos ? findByOrder(root, pos) : null;
        }

        // get i-th
        private int findByOrder(Node cur, int pos) {
            if (size(cur.left) > pos)
                return findByOrder(cur.left, pos);

            if (size(cur.left) == pos)
                return cur.key;

            // size(cur.left) < pos
            return findByOrder(cur.right, pos - 1 - size(cur.left));
        }
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Solution().run();
    }
}