На склад только что прибыли $n$ посылок, пронумерованных от $1$ до $n$. Они поступили в порядке $a_1, \dots, a_n$, и мы хотим отсортировать их так, чтобы они располагались в порядке $1, 2, \dots, n$.

Сортировочная машина на складе работает по фазам. Каждая фаза принимает на вход ряд посылок $a_1, \dots, a_n$ и действует следующим образом: сначала первая посылка $a_1$ помещается в новый ряд. Затем для каждой посылки $a_i$ при $i = 2, \dots, n$, если $a_i$ больше последней (самой правой) посылки в новом ряду, машина кладёт её в конец ряда. В противном случае она кладёт её в начало ряда.

Если новый ряд не отсортирован, он подаётся на вход следующей фазе сортировочной машины.

Напишите программу, которая поможет протестировать, работает ли машина так, как задумано, отвечая на запросы вида «какая посылка находится на $b$-м месте после $t$ фаз».

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

Первая строка входных данных содержит два целых числа $n$ и $q$ ($1 \le n, q \le 5 \cdot 10^5$), обозначающих количество посылок и количество запросов соответственно.

Вторая строка содержит последовательность из $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$), представляющую начальный порядок посылок.

Следующие $q$ строк содержат запросы; $i$-я строка содержит два целых числа $t_i$ и $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), описывающих $i$-й запрос.

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

Выведите ровно $q$ строк. В $i$-й строке должен содержаться ответ на $i$-й запрос.

Если машина выполнила меньше $t_i$ фаз, выведите $-1$. Иначе выведите номер посылки, которая находится на позиции $b_i$ слева после выполнения $t_i$ фаз.

Примеры

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

5 4
2 1 3 5 4
1 1
3 2
4 1
0 4

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

4
2
-1
5

Примечание 1

Машина выполнит три фазы:

$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$

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

1 1
1
1 1

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

-1