BOB (Bank of Byteland) is the only bank in the land of byteland. Hence million of transactions take place every day. You are currently the manager in charge of BOB. Being bored one day you took all the transaction of that day and asked your friend Codemonk to ask Q queries on the data . Codemonk being a exceptionally good coder gave you two numbers M and N. He then asks you to tell him N^th transaction having cost more than or equal to M maintaining the order of transaction if it exist else print 1. Can you answer all of his queries.

Input

First line of input contains T and Q i.e number of transaction and number of queries,
Next line contains T intergers representing cost of each transaction,
Next Q lines contains two integers representing M and N. 

Output

For each query print the cost of required transaction if it exists else print -1.

Constraints

$1<=T<=100000$

$1<=Q<=100000$

$1<=Cost$ $of$ $each$ $transaction$ $<=100000$

$1<=M,N<=100000$