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

这是该问题的困难版本。在此版本中，$1 \le n, m \le 2\cdot10^5$。如果你已锁定本题，则你可以对本题进行 Hack；但你仅在同时锁定本题及前一题的情况下，才能对前一题进行 Hack。

给定一个长度为 $n$ 的整数序列 $a=[a_1,a_2,\dots,a_n]$。它的子序列是通过从序列 $a$ 中删除零个或多个元素（这些被删元素不必连续）而得到的。例如，对于序列 $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]$ 都是子序列（以上仅为所有可能子序列中的一部分）；
• $[40]$、$[33,33]$、$[33,20,20]$、$[20,20,11,11]$ 则不是子序列。

假设额外给定一个非负整数 $k$（$1 \le k \le n$），则称一个子序列为最优子序列，当且仅当满足以下两个条件：

• 它的长度恰好为 $k$，且其元素之和在所有长度为 $k$ 的子序列中达到最大；
• 在所有满足上一条的长度为 $k$ 的子序列中，它在字典序意义上最小。

回顾定义：序列 $b=[b_1, b_2, \dots, b_k]$ 字典序小于序列 $c=[c_1, c_2, \dots, c_k]$，当且仅当存在某个下标 $t$（$1 \le t \le k$），使得 $b_1=c_1$, $b_2=c_2$, ..., $b_{t-1}=c_{t-1}$，且同时 $b_t \lt c_t$。例如：

• $[10, 20, 20]$ 字典序小于 $[10, 21, 1]$，
• $[7, 99, 99]$ 字典序小于 $[10, 21, 1]$，
• $[10, 21, 0]$ 字典序小于 $[10, 21, 1]$。

给定序列 $a=[a_1,a_2,\dots,a_n]$ 和 $m$ 个查询，每个查询由两个整数 $k_j$ 和 $pos_j$ 组成（$1 \le k_j \le n$, $1 \le pos_j \le k_j$）。对每个查询，请输出：在序列 $a$ 对应 $k = k_j$ 的最优子序列中，位于位置 $pos_j$（从 1 开始计数）处的元素值。

例如，若 $n=4$，$a=[10,20,30,20]$，$k_j=2$，则最优子序列为 $[20,30]$ —— 它是在所有长度为 $2$ 且元素和最大的子序列中字典序最小的一个。因此，查询 $k_j=2$, $pos_j=1$ 的答案是 $20$，而查询 $k_j=2$, $pos_j=2$ 的答案是 $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.

第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）——序列 $a$ 的长度。

第二行包含序列 $a$ 的元素：整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

第三行包含一个整数 $m$（$1 \le m \le 2\cdot10^5$）——请求的个数。

接下来的 $m$ 行每行包含一对整数 $k_j$ 和 $pos_j$（$1 \le k_j \le n$, $1 \le pos_j \le k_j$）——这些请求。

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

每行输出 $m$ 个整数 $r_1, r_2, \dots, r_m$（$1 \le r_j \le 10^9$）：按输入中请求出现的顺序给出各请求的答案。其中 $r_j$ 的值应等于在 $k=k_j$ 时最优子序列中位置 $pos_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]$.

在第一个例子中，对于 $a=[10,20,10]$，最优子序列如下：

• 当 $k=1$ 时：$[20]$，
• 当 $k=2$ 时：$[10,20]$，
• 当 $k=3$ 时：$[10,20,10]$。