There are $n$ parcels, numbered from $1$ to $n$, that just arrived to a warehouse. They came in the order $a_1, \dots, a_n$, and we want to sort them so that they are in the order $1, 2, \dots, n$.

The sorting machine in the warehouse works in phases. Each phase accepts a row $a_1, \dots, a_n$ of parcels and proceeds as follows: First, the first parcel $a_1$ is put into a new row. Then, for every parcel $a_i$ for $i = 2, \dots, n$, if $a_i$ is greater than the last (rightmost) parcel in the new row, it puts it at the end of the row. Otherwise, it puts it at the front of the row.

If the new row is not sorted, it serves as the input for the next phase of the sorting machine.

Write a program that helps testing whether the machine works as intended by answering queries of the form "which parcel is at the $b$-th place after $t$ phases".

Input

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

The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) that represent the initial ordering of the parcels.

The next $q$ lines contain queries; the $i$-th line contains two integers $t_i$ and $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), denoting the $i$-th query.

Output

Output exactly $q$ lines. The $i$-th line should contain the answer to the $i$-th query.

If the machine performed less than $t_i$ phases, write $-1$. Otherwise, write which parcel is at the position $b_i$ from left, after $t_i$ phases have been performed.

Examples

Input 1

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

Output 1

4
2
-1
5

Note 1

The machine will perform three phases:

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

Input 2

1 1
1
1 1

Output 2

-1