C. Турнир по борьбе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бурёнка пришла смотреть самое интересное спортивное событие года — турнир по борьбе, организованный её другом Тоней.

В турнире участвует $$$n$$$ спортсменов, им были выданы номера от $$$1$$$ до $$$n$$$. Для спортсмена с $$$i$$$-м номером Бурёнка определила его силу — целое число $$$a_i$$$, где $$$1 \leq a_i \leq n$$$. Все силы различны, то есть массив сил $$$a$$$ является перестановкой длины $$$n$$$. Известно, что если $$$a_i > a_j$$$, то $$$i$$$-й участник всегда побеждает $$$j$$$-го

Турнир проходит так: сначала все $$$n$$$ спортсменов встают в очередь по возрастанию своих номеров, а затем происходит бесконечно много туров. В каждом туре происходит ровно один поединок между первыми двумя спортсменами из очереди. Победитель возвращается в начало очереди, а проигравший встаёт в её конец.

Бурёнка решила задать Тоне $$$q$$$ вопросов. В каждом вопросе Бурёнка спрашивает, сколько побед $$$i$$$-й спортсмен одержит за первые $$$k$$$ туров соревнования для некоторых $$$i$$$ и $$$k$$$. Тоня не очень хорош в аналитике, поэтому просит вас помочь ему с ответом на все вопросы.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — количество участников турнира и число вопросов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$a$$$, являющийся перестановкой.

Следующие $$$q$$$ строк набора входных данных содержат вопросы. Каждая строка содержит два целых числа $$$i$$$ и $$$k$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq k \leq 10^9$$$) — номер участника и число туров.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превосходят $$$10^5$$$.

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

На каждый вопрос Бурёнки выведите единственную строку, содержащую одно целое число — ответ на вопрос.

Пример
Входные данные
3
3 1
3 1 2
1 2
4 2
1 3 4 2
4 5
3 2
5 2
1 2 3 5 4
5 1000000000
4 6
Выходные данные
2
0
1
0
4
Примечание

В первом наборе входных данных первый по номеру спортсмен имеет силу $$$3$$$, в первом туре он победит спортсмена с номером $$$2$$$ и силой $$$1$$$, а во втором — спортсмена с номером $$$3$$$ и силой $$$2$$$.

Во втором наборе входных данных перечислим силы спортсменов, дерущихся в первых $$$5$$$ боях: $$$1$$$ и $$$3$$$, $$$3$$$ и $$$4$$$, $$$4$$$ и $$$2$$$, $$$4$$$ и $$$1$$$, $$$4$$$ и $$$3$$$. Участник с номером $$$4$$$ в первых $$$5$$$ турах одержал $$$0$$$ побед (его сила равна $$$2$$$). Участник с номером $$$3$$$ имеет силу $$$4$$$ и в первых двух боях одержал $$$1$$$ победу, проведя $$$1$$$ бой.