有 $n$ 个包裹，编号为 $1$ 到 $n$，刚刚到达一个仓库。它们以 $a_1, \dots, a_n$ 的顺序到达，我们希望将它们排序，使得它们的顺序为 $1, 2, \dots, n$。

仓库中的分拣机分阶段工作。每个阶段接收一排包裹 $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$ 行包含两个整数 $t_i$ 和 $b_i$ ($0 \le t_i \le 10^9$，$1 \le b_i \le n$)，表示第 $i$ 个查询。

输出格式

输出恰好 $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