Il y a $n$ colis, numérotés de $1$ à $n$, qui viennent d'arriver dans un entrepôt. Ils sont arrivés dans l'ordre $a_1, \dots, a_n$, et nous voulons les trier de sorte qu'ils soient dans l'ordre $1, 2, \dots, n$.

La machine de tri de l'entrepôt fonctionne par phases. Chaque phase accepte une rangée $a_1, \dots, a_n$ de colis et procède comme suit : tout d'abord, le premier colis $a_1$ est placé dans une nouvelle rangée. Ensuite, pour chaque colis $a_i$ pour $i = 2, \dots, n$, si $a_i$ est supérieur au dernier colis (le plus à droite) de la nouvelle rangée, elle le place à la fin de la rangée. Sinon, elle le place au début de la rangée.

Si la nouvelle rangée n'est pas triée, elle sert d'entrée pour la phase suivante de la machine de tri.

Écrivez un programme qui aide à tester si la machine fonctionne comme prévu en répondant à des requêtes de la forme « quel colis se trouve à la $b$-ème place après $t$ phases ».

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $q$ ($1 \le n, q \le 5 \cdot 10^5$), désignant respectivement le nombre de colis et le nombre de requêtes.

La deuxième ligne contient une séquence de $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) représentant l'ordre initial des colis.

Les $q$ lignes suivantes contiennent les requêtes ; la $i$-ème ligne contient deux entiers $t_i$ et $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), désignant la $i$-ème requête.

Sortie

Affichez exactement $q$ lignes. La $i$-ème ligne doit contenir la réponse à la $i$-ème requête.

Si la machine a effectué moins de $t_i$ phases, écrivez $-1$. Sinon, écrivez quel colis se trouve à la position $b_i$ en partant de la gauche, après que $t_i$ phases ont été effectuées.

Exemples

Entrée 1

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

Sortie 1

4
2
-1
5

Note 1

La machine effectuera trois phases :

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

Entrée 2

1 1
1
1 1

Sortie 2

-1