Optimal Subsequences (Hard Version)
Contest: Technocup 2020 - Elimination Round 3
Difficulty rating: 1800
Tags: data structures, greedy

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3

Example output:
20
10
20
10
20
10

Example 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

Example output:
2
3
2
3
2
3
1
1
3

Editorial:
Let's first solve the simplified version (Easy Version) without paying attention to the efficiency of the algorithm.
It is clear that the sum of the elements of the optimal subsequence is equal to the sum of $$$k$$$ maximal elements of the sequence $$$a$$$. Let the smallest (the $$$k$$$-th) of $$$k$$$ maximal elements be $$$x$$$. Obviously, all elements of $$$a$$$ that are greater than $$$x$$$ and several elements that are equal to $$$x$$$ will be included in the optimal subsequence. Among all the elements that are equal to $$$x$$$ you need to choose those that are located to the left. Thus, a simplified version solution might look like this:
• in order to build an optimal subsequence of length $$$k$$$, take an array $$$a$$$ and construct its copy $$$b$$$ sorted by non-increasing: $$$b_1 \ge b_2 \ge \dots \ge b_n$$$;
• let $$$x = b_k$$$;
• we take the following subsequence from $$$a$$$: all the elements $$$a_i > x$$$ and several leftmost occurrences of $$$a_i = x$$$ (you need to take such occurrences in order to get exactly $$$k$$$ elements in total).
To solve the complicated version, we note that the solution above is equivalent to sorting all elements of $$$a$$$ first of all by value (non-increasing), and secondly by position (ascending). The desired optimal subsequence is simply $$$k$$$ first elements of $$$a$$$ in this order.
To quickly process requests, we will use the opportunity to read all requests in the program, sort them by $$$k_j$$$ and process them in that order. Then, in order to answer the request $$$k_j$$$, $$$pos_j$$$ you need to take $$$k_j$$$ elements in this order and choose the $$$pos_j$$$-th from them (just in the order of indices). Thus, the problem is reduced to finding the $$$pos$$$-th element in a set, where only elements are added. This can be solved using a wide range of data structures (a tree of segments, a Fenwick tree, even sqrt-compositions), and using a non-standard tree built into g++ that supports the operation "quickly find the $$$pos$$$ th element of a set". Below is the solution code: