D2. Оптимальные подпоследовательности (усложненная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложненная версия задачи, в этой версии $$$1 \le n, m \le 2\cdot10^5$$$. Вы можете взламывать эту задачу, если вы ее заблокировали. Но вы можете взламывать предыдущую версию задачи, только если вы заблокировали обе версии.

Пусть задана последовательность целых чисел $$$a=[a_1,a_2,\dots,a_n]$$$ длины $$$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]$$$, если первый слева элемент в котором они различаются меньше в последовательности $$$b$$$ чем в $$$c$$$. Формально: существует такое $$$t$$$ ($$$1 \le t \le k$$$), что $$$b_1=c_1$$$, $$$b_2=c_2$$$, ..., $$$b_{t-1}=c_{t-1}$$$ и одновременно $$$b_t<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 \le n$$$, $$$1 \le pos_j \le k_j$$$). Для каждого запроса выведите значение, которое стоит в индексе $$$pos_j$$$ оптимальной подпоследовательности заданной последовательности $$$a$$$ для $$$k=k_j$$$.

Например, если $$$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$$$.

Входные данные

В первой строке записано целое число $$$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 \le n$$$, $$$1 \le pos_j \le k_j$$$) — параметры запросов.

Выходные данные

Выведите $$$m$$$ целых чисел $$$r_1, r_2, \dots, r_m$$$ ($$$1 \le r_j \le 10^9$$$) по одному в строке — ответы на запросы в порядке их следования во входных данных. Значение $$$r_j$$$ должно быть равно значению, которое содержится в позиции $$$pos_j$$$ оптимальной подпоследовательности для $$$k=k_j$$$.

Примеры
Входные данные
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3
Выходные данные
20
10
20
10
20
10
Входные данные
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
Выходные данные
2
3
2
3
2
3
1
1
3
Примечание

В первом примере, для $$$a=[10,20,10]$$$ оптимальные подпоследовательности:

  • для $$$k=1$$$ — это $$$[20]$$$,
  • для $$$k=2$$$ — это $$$[10,20]$$$,
  • для $$$k=3$$$ — это $$$[10,20,10]$$$.