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$.Examplesinput
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]$.
Solution:
#include <bits/stdc++.h> using namespace std; template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int m; cin >> m; vector<int> k(m), pos(m); vector<vector<int>> at(n); for (int i = 0; i < m; i++) { cin >> k[i] >> pos[i]; --k[i]; --pos[i]; at[k[i]].push_back(i); } vector<int> order(n); for (int i = 0; i < n; i++) { order[i] = i; } sort(order.begin(), order.end(), [&](int i, int j) { if (a[i] != a[j]) { return a[i] > a[j]; } return i < j; }); vector<int> res(m); fenwick<int> fenw(n); for (int i = 0; i < n; i++) { fenw.modify(order[i], 1); for (int j : at[i]) { int low = 0, high = n - 1; while (low < high) { int mid = (low + high) >> 1; if (fenw.get(mid) >= pos[j] + 1) { high = mid; } else { low = mid + 1; } } res[j] = a[low]; } } for (int i = 0; i < m; i++) { cout << res[i] << '\n'; } return 0; }