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