L. Timetable Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a bus stop where exactly one bus arrives every minute.

Thus, a timetable is necessary for the passengers.

There are $$$n$$$ minutes in one day, so the timetable is an array $$$a$$$ containing $$$n$$$ integers. let $$$a_i$$$ be the $$$i$$$-th number in array $$$a$$$, denoting that a bus with its number $$$a_i$$$ arrives exactly on the $$$i$$$-th minute.

There will be $$$q$$$ queries, each query will ask you when is the $$$y$$$-th time does the bus with number $$$x$$$ arrive in one day?

Input

The first line contains two integers, $$$n$$$ $$$(1\le n\le 10^5)$$$ and $$$q$$$ $$$(1\le q \le 10^5)$$$, denoting the length of the timetable and the number of queries.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is $$$a_i$$$ $$$(1\le a_i \le 10^9)$$$, denoting the bus with number $$$a_i$$$ arrives on the $$$i$$$-th minute.

For the next $$$q$$$ lines, each line contains two integers, $$$x$$$ $$$(1\le x\le 10^9)$$$ and $$$y$$$ $$$(1\le y\le 10^5)$$$, denoting there is an query, asking you when is the $$$y$$$-th time does the bus numbered $$$x$$$ arrive.

Output

For each query, you should output one line containing exactly one integer, denoting your answer for this query. If the $$$x$$$-th bus arrives less than $$$y$$$ times in one day according to the timetable, output $$$-1$$$.

Examples
Input
10 5
1 2 3 4 5 5 4 3 2 1
1 1
1 2
1 3
6 1
5 2
Output
1
10
-1
-1
6
Input
10 5
1 2 1 2 1 2 3 3 3 1
1 4
1 5
3 3
3 4
2 2
Output
10
-1
9
-1
4