D2. Optimal Subsequences (Hard Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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