$1$부터 $n$까지 번호가 매겨진 $n$개의 소포가 방금 창고에 도착했습니다. 소포들은 $a_1, \dots, a_n$의 순서로 도착했으며, 우리는 이들을 $1, 2, \dots, n$의 순서가 되도록 정렬하고 싶습니다.

창고의 분류 기계는 단계(phase)별로 작동합니다. 각 단계는 일렬로 놓인 소포 $a_1, \dots, a_n$을 입력받아 다음과 같이 진행합니다: 먼저 첫 번째 소포 $a_1$을 새로운 줄에 놓습니다. 그런 다음 $i = 2, \dots, n$인 각 소포 $a_i$에 대해, 만약 $a_i$가 새로운 줄의 마지막(가장 오른쪽) 소포보다 크다면 줄의 맨 뒤에 놓습니다. 그렇지 않으면 줄의 맨 앞에 놓습니다.

만약 새로운 줄이 정렬되지 않았다면, 그 줄은 분류 기계의 다음 단계의 입력으로 사용됩니다.

"$t$번의 단계를 거친 후 $b$번째 위치에 있는 소포는 무엇인가"라는 형태의 질의에 답함으로써 기계가 의도한 대로 작동하는지 테스트하는 프로그램을 작성하십시오.

입력

입력의 첫째 줄에는 소포의 개수와 질의의 개수를 각각 나타내는 두 정수 $n$과 $q$ ($1 \le n, q \le 5 \cdot 10^5$)가 주어집니다.

둘째 줄에는 소포들의 초기 순서를 나타내는 $n$개의 정수로 이루어진 수열 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$)이 주어집니다.

다음 $q$개의 줄에는 질의가 주어집니다. $i$번째 줄에는 $i$번째 질의를 나타내는 두 정수 $t_i$와 $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$)가 주어집니다.

출력

정확히 $q$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 질의에 대한 답을 출력해야 합니다.

기계가 수행한 단계 수가 $t_i$보다 적다면 $-1$을 출력합니다. 그렇지 않다면, $t_i$번의 단계가 수행된 후 왼쪽에서 $b_i$번째 위치에 있는 소포가 무엇인지 출력합니다.

예제

예제 입력 1

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

예제 출력 1

4
2
-1
5

노트 1

기계는 세 단계를 수행합니다:

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

예제 입력 2

1 1
1
1 1

예제 출력 2

-1