Do magazynu właśnie dotarło $n$ paczek ponumerowanych od $1$ do $n$. Przybyły one w kolejności $a_1, \dots, a_n$, a my chcemy je posortować tak, aby ustawiły się w kolejności $1, 2, \dots, n$.

Maszyna sortująca w magazynie działa w fazach. Każda faza przyjmuje rząd paczek $a_1, \dots, a_n$ i postępuje następująco: Najpierw pierwsza paczka $a_1$ jest umieszczana w nowym rzędzie. Następnie dla każdej paczki $a_i$ dla $i = 2, \dots, n$, jeśli $a_i$ jest większa od ostatniej (skrajnie prawej) paczki w nowym rzędzie, maszyna umieszcza ją na końcu rzędu. W przeciwnym razie umieszcza ją na początku rzędu.

Jeśli nowy rząd nie jest posortowany, służy on jako wejście dla kolejnej fazy maszyny sortującej.

Napisz program pomagający przetestować, czy maszyna działa zgodnie z założeniami, odpowiadając na zapytania postaci „która paczka znajduje się na $b$-tym miejscu po $t$ fazach”.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ oraz $q$ ($1 \le n, q \le 5 \cdot 10^5$), oznaczające odpowiednio liczbę paczek oraz liczbę zapytań.

Drugi wiersz zawiera ciąg $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$), które reprezentują początkowe ustawienie paczek.

Kolejne $q$ wierszy zawiera zapytania; $i$-ty wiersz zawiera dwie liczby całkowite $t_i$ oraz $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), oznaczające $i$-te zapytanie.

Wyjście

Wypisz dokładnie $q$ wierszy. $i$-ty wiersz powinien zawierać odpowiedź na $i$-te zapytanie.

Jeśli maszyna wykonała mniej niż $t_i$ faz, wypisz $-1$. W przeciwnym razie wypisz, która paczka znajduje się na pozycji $b_i$ od lewej po wykonaniu $t_i$ faz.

Przykłady

Wejście 1

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

Wyjście 1

4
2
-1
5

Uwaga 1

Maszyna wykona trzy fazy:

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

Wejście 2

1 1
1
1 1

Wyjście 2

-1