CF1227D2.Optimal Subsequences (Hard Version)

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$ .

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.

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$ .

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]$ .