Hay $n$ paquetes, numerados del $1$ al $n$, que acaban de llegar a un almacén. Llegaron en el orden $a_1, \dots, a_n$, y queremos ordenarlos para que queden en el orden $1, 2, \dots, n$.

La máquina clasificadora del almacén funciona por fases. Cada fase acepta una fila $a_1, \dots, a_n$ de paquetes y procede de la siguiente manera: Primero, el primer paquete $a_1$ se coloca en una nueva fila. Luego, para cada paquete $a_i$ con $i = 2, \dots, n$, si $a_i$ es mayor que el último paquete (el de más a la derecha) en la nueva fila, lo coloca al final de la fila. De lo contrario, lo coloca al principio de la fila.

Si la nueva fila no está ordenada, sirve como entrada para la siguiente fase de la máquina clasificadora.

Escribe un programa que ayude a probar si la máquina funciona como se espera respondiendo consultas de la forma «qué paquete está en el $b$-ésimo lugar después de $t$ fases».

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $q$ ($1 \le n, q \le 5 \cdot 10^5$), que denotan el número de paquetes y el número de consultas, respectivamente.

La segunda línea contiene una secuencia de $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) que representan el orden inicial de los paquetes.

Las siguientes $q$ líneas contienen las consultas; la $i$-ésima línea contiene dos enteros $t_i$ y $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), que denotan la $i$-ésima consulta.

Salida

Imprime exactamente $q$ líneas. La $i$-ésima línea debe contener la respuesta a la $i$-ésima consulta.

Si la máquina realizó menos de $t_i$ fases, escribe $-1$. De lo contrario, escribe qué paquete se encuentra en la posición $b_i$ desde la izquierda, después de haberse realizado $t_i$ fases.

Ejemplos

Entrada 1

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

Salida 1

4
2
-1
5

Nota 1

La máquina realizará tres fases:

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

Entrada 2

1 1
1
1 1

Salida 2

-1