This is the harder version of the problem. In this version, $1 \le n, m \le 2\cdot10^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,\dots,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 \le k \le 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, \dots, b_k]$ is lexicographically smaller than the sequence $c=[c_1, c_2, \dots, 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 \le t \le 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,\dots,a_n]$ and $m$ requests, each consisting of two numbers $k_j$ and $pos_j$ ($1 \le k \le n$, $1 \le pos_j \le 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 \le n \le 2\cdot10^5$) — the length of the sequence $a$.

The second line contains elements of the sequence $a$: integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The third line contains an integer $m$ ($1 \le m \le 2\cdot10^5$) — the number of requests.

The following $m$ lines contain pairs of integers $k_j$ and $pos_j$ ($1 \le k \le n$, $1 \le pos_j \le k_j$) — the requests.


-----Output-----

Print $m$ integers $r_1, r_2, \dots, r_m$ ($1 \le r_j \le 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]$.

Difficulty: interview

Starter code:

Solutions:
import sys

class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1


class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                    self._rotate_right(n.right)
                self._rotate_left(n)
            else:
                n = n.parent

    def _remove_one(self, node):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        replacement = node.left or node.right
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = replacement
            else:
                node.parent.right = replacement
            replacement.parent = node.parent
            node.parent = None
        else:
            self._tree = replacement
            replacement.parent = None
        node.left = None
        node.right = None
        node.parent = None
        self._rebalance(replacement)

    def _remove_leaf(self, node):
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = None
            else:
                node.parent.right = None
            self._rebalance(node.parent)
        else:
            self._tree = None
        node.parent = None
        node.left = None
        node.right = None

    def remove(self, k):
        node = self._get_node(k)
        if not node:
            return
        if AvlTree._is_leaf(node):
            self._remove_leaf(node)
            return
        if node.left and node.right:
            nxt = AvlTree._get_next(node)
            node.key = nxt.key
            node.value = nxt.value
            if self._is_leaf(nxt):
                self._remove_leaf(nxt)
            else:
                self._remove_one(nxt)
            self._rebalance(node)
        else:
            self._remove_one(node)

    def get(self, k):
        node = self._get_node(k)
        return node.value if node else -1

    def _get_node(self, k):
        if not self._tree:
            return None
        node = self._tree
        while node:
            if k < node.key:
                node = node.left
            elif node.key < k:
                node = node.right
            else:
                return node
        return None

    def get_at(self, pos):
        x = pos + 1
        node = self._tree
        while node:
            if x < node.num_left:
                node = node.left
            elif node.num_left < x:
                x -= node.num_left
                node = node.right
            else:
                return (node.key, node.value)
        raise IndexError("Out of ranges")

    @staticmethod
    def _is_left(node):
        return node.parent.left and node.parent.left == node

    @staticmethod
    def _is_leaf(node):
        return node.left is None and node.right is None

    def _rotate_right(self, node):
        if not node.parent:
            self._tree = node.left
            node.left.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.left
            node.left.parent = node.parent
        else:
            node.parent.right = node.left
            node.left.parent = node.parent
        bk = node.left.right
        node.left.right = node
        node.parent = node.left
        node.left = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    def _rotate_left(self, node):
        if not node.parent:
            self._tree = node.right
            node.right.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.right
            node.right.parent = node.parent
        else:
            node.parent.right = node.right
            node.right.parent = node.parent
        bk = node.right.left
        node.right.left = node
        node.parent = node.right
        node.right = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    @staticmethod
    def _get_next(node):
        if not node.right:
            return node.parent
        n = node.right
        while n.left:
            n = n.left
        return n


def __starting_point():
    lines = sys.stdin.readlines()
    n = int(lines[0])
    aa = [(a, i) for i, a in enumerate(map(int, lines[1].split()))]
    m = int(lines[2])
    qs = [None]*m
    ans = [None]*m
    for i in range(m):
        k, pos = list(map(int, lines[i+3].split()))
        qs[i] = (pos, k, i)
    qs.sort(key=lambda x: x[1])
    aa.sort(key=lambda x: x[1])
    aa.sort(key=lambda x: x[0], reverse=True)
    avl = AvlTree()
    s = 0
    for pos, k, i in qs:
        for a, j in aa[s: k]:
            avl.add(j, a)
        ans[i] = str(avl.get_at(pos - 1)[1])
        s = k
    print("\n".join(ans))


__starting_point()

WIDTH = 10

def index_tree(n):
    levels = [ [1]*n ]

    size = WIDTH
    while size < n:
        m, r = n // size, n % size
        levels.append( [size]*m + ([r] if r > 0 else []) )
        size *= WIDTH

    return levels

def dec_index(levels, i):
    for level in levels:
        level[i] -= 1
        i //= WIDTH

def find_pos(levels, pos):
    i, l = 0, len(levels) - 1
    
    total = 0
    while True:
        level = levels[l]
        while total + level[i] < pos:
            total += level[i]
            i += 1
        
        if l == 0: return i
        i *= WIDTH
        l -= 1


import sys

def main():
    ## INPUT
    numbers = [int(x) for x in sys.stdin.read().split()]
    n = numbers[0]
    sequence = numbers[1:n+1]
    m = numbers[n+1]

    queries = {}
    for i in range(n+2, n+2 + 2*m, 2):
        k, pos = numbers[i], numbers[i+1]
        if k in queries: queries[k][pos] = None
        else: queries[k] = { pos: None }
    
    ## WORK
    sequence1 = sorted([ (s,-i) for i,s in enumerate(sequence) ])
    tree = index_tree(n)
    size = n

    for _, neg_i in sequence1: 
        if size in queries:
            for pos in queries[size]:
                queries[size][pos] = find_pos(tree, pos)

        dec_index(tree, -neg_i)
        size -= 1

    ## PRINT 
    for i in range(n+2, n+2 + 2*m, 2):
        k, pos = numbers[i], numbers[i+1]
        print(sequence[ queries[k][pos] ])


main()



from collections import defaultdict
import sys as _sys


def main():
    n, = _read_ints()
    a = tuple(_read_ints())
    m, = _read_ints()
    queries = (tuple(_read_ints()) for i_query in range(m))
    result = process_queries(a, queries)
    print(*result, sep='\n')


def _read_line():
    result = _sys.stdin.readline()
    assert result[-1] == "\n"
    return result[:-1]


def _read_ints():
    return map(int, _read_line().split())


def process_queries(sequence, queries):
    sequence = tuple(sequence)
    
    indices_by_values = defaultdict(list)
    for i, x in enumerate(sequence):
        indices_by_values[x].append(i)
    
    enumerated_queries = sorted(enumerate(queries), key=lambda iv: iv[1][0])[::-1]
    queries_responses = [None] * len(enumerated_queries)
    
    selections_tree = [0] * (len(sequence) + 1)
    
    k = 0
    for value, indices in sorted(indices_by_values.items(), reverse=True):
        for index_to_select in indices:
            _fenwick_tree_add(selections_tree, index_to_select, 1)
            k += 1
            while enumerated_queries and enumerated_queries[-1][1][0] == k:
                query_index, (_k, subseq_index) = enumerated_queries.pop()
                seq_index = _find_seq_index_by_subseq_index(selections_tree, subseq_index)
                queries_responses[query_index] = sequence[seq_index]

    return queries_responses


def _find_seq_index_by_subseq_index(tree, subseq_i):
    min_i = 0
    max_i = len(tree) - 1
    while min_i != max_i:
        mid_i = (min_i + max_i) // 2
        if _fenwick_tree_prefix_sum(tree, mid_i) < subseq_i:
            min_i = mid_i + 1
        else:
            max_i = mid_i
    return min_i


def _fenwick_tree_prefix_sum(tree, i):
    i += 1
    result = 0
    while i != 0:
        result += tree[i]
        i -= i & (-i)
    return result


def _fenwick_tree_add(tree, i, x):
    i += 1
    while i < len(tree):
        tree[i] += x
        i += i & (-i)


def __starting_point():
    main()

__starting_point()

import sys as _sys


def main():
    n, = _read_ints()
    a = tuple(_read_ints())
    m, = _read_ints()
    queries = (tuple(_read_ints()) for i_query in range(m))
    result = process_queries(a, queries)
    print(*result, sep='\n')


def _read_line():
    result = _sys.stdin.readline()
    assert result[-1] == "\n"
    return result[:-1]


def _read_ints():
    return map(int, _read_line().split())


def process_queries(sequence, queries):
    sequence = tuple(sequence)
    
    indices_to_select = sorted(
        range(len(sequence)),
        key=lambda index: (-sequence[index], index)
    )
    
    enumerated_queries = sorted(enumerate(queries), key=lambda iv: iv[1][0])[::-1]
    queries_responses = [None] * len(enumerated_queries)
    
    selections_tree = [0] * (len(sequence) + 1)
    
    selected_n = 0
    for index_to_select in indices_to_select:
        _fenwick_tree_add(selections_tree, index_to_select, 1)
        selected_n += 1
        while enumerated_queries and enumerated_queries[-1][1][0] == selected_n:
            query_index, (_k, subseq_index) = enumerated_queries.pop()
            seq_index = _find_seq_index_by_subseq_index(selections_tree, subseq_index)
            queries_responses[query_index] = sequence[seq_index]
    
    return queries_responses


def _find_seq_index_by_subseq_index(tree, subseq_i):
    seq_length = len(tree) - 1
    min_i = 0
    max_i = seq_length - 1
    while min_i != max_i:
        mid_i = (min_i + max_i) // 2
        if _fenwick_tree_prefix_sum(tree, mid_i) < subseq_i:
            min_i = mid_i + 1
        else:
            max_i = mid_i
    return min_i


def _fenwick_tree_prefix_sum(tree, i):
    i += 1
    result = 0
    while i != 0:
        result += tree[i]
        i -= i & (-i)
    return result


def _fenwick_tree_add(tree, i, x):
    i += 1
    while i < len(tree):
        tree[i] += x
        i += i & (-i)


def __starting_point():
    main()

__starting_point()