На склад щойно прибули $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