Ci sono $n$ pacchi, numerati da $1$ a $n$, appena arrivati in un magazzino. Sono arrivati nell'ordine $a_1, \dots, a_n$ e vogliamo ordinarli in modo che siano nell'ordine $1, 2, \dots, n$.

La macchina smistatrice nel magazzino lavora in fasi. Ogni fase accetta una fila $a_1, \dots, a_n$ di pacchi e procede come segue: Prima il primo pacco $a_1$ viene messo in una nuova fila. Poi, per ogni pacco $a_i$ per $i = 2, \dots, n$, se $a_i$ è maggiore dell'ultimo pacco (quello più a destra) nella nuova fila, lo mette alla fine della fila. Altrimenti, lo mette all'inizio della fila.

Se la nuova fila non è ordinata, funge da input per la fase successiva della macchina smistatrice.

Scrivi un programma che aiuti a verificare se la macchina funziona come previsto rispondendo a query della forma "quale pacco si trova al $b$-esimo posto dopo $t$ fasi".

Input

La prima riga dell'input contiene due interi $n$ e $q$ ($1 \le n, q \le 5 \cdot 10^5$), che indicano rispettivamente il numero di pacchi e il numero di query.

La seconda riga contiene una sequenza di $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) che rappresentano l'ordinamento iniziale dei pacchi.

Le successive $q$ righe contengono le query; la $i$-esima riga contiene due interi $t_i$ e $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), che indicano la $i$-esima query.

Output

Stampa esattamente $q$ righe. La $i$-esima riga deve contenere la risposta alla $i$-esima query.

Se la macchina ha eseguito meno di $t_i$ fasi, scrivi $-1$. Altrimenti, scrivi quale pacco si trova nella posizione $b_i$ da sinistra, dopo che sono state eseguite $t_i$ fasi.

Esempi

Input 1

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

Output 1

4
2
-1
5

Note 1

La macchina eseguirà tre fasi:

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

Input 2

1 1
1
1 1

Output 2

-1