Queries Especiais

Time limit: 2000 msMemory limit: 256 MB

Você recebe um array $A$ com $N$ inteiros.

Você deve responder $Q$ consultas. Em cada consulta, são dados dois inteiros $L$ e $X$ .

Para cada consulta, encontre o menor índice $i$ tal que $i > L$ e $A_i > X$ .

Se tal índice não existir, imprima $-1$ .

Input

A primeira linha contém dois inteiros $N$ e $Q$ $(1 \le N, Q \le 2 \cdot 10^5)$ — o tamanho do array e o número de consultas.

Output

Para cada consulta, imprima o menor índice $i$ tal que $i > L$ e $A_i > X$ , ou $-1$ se não existir tal índice.

Samples

Sample 1

Input

7 4
2 8 3 5 1 9 6
2 4
3 8
5 5
6 10

Output

Na primeira consulta, procuramos a primeira posição depois de $2$ cujo valor seja maior que $4$ . A posição $3$ contém $3$ , enquanto a posição $4$ contém $5$ . Portanto, a resposta é .

Queries Especiais

Input

Output

Samples

Sample 1

Submit

Submissions