Это усложненная версия задачи, в этой версии $$$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$$$.