$1$ から $n$ までの番号が付けられた $n$ 個の小包が、ちょうど倉庫に到着しました。それらは $a_1, \dots, a_n$ の順で到着しましたが、私たちはそれらを $1, 2, \dots, n$ の順になるように並べ替えたいと考えています。

倉庫の仕分け機はフェーズ単位で動作します。各フェーズでは 1 列の小包 $a_1, \dots, a_n$ を受け取り、次のように処理を進めます：まず、最初の小包 $a_1$ を新しい列に入れます。次に、$i = 2, \dots, n$ の各小包 $a_i$ について、もし $a_i$ が新しい列の最後（一番右）の小包より大きければ、それを列の末尾に置きます。そうでなければ、列の先頭に置きます。

新しい列がまだ整列されていない場合、その列が仕分け機の次のフェーズの入力となります。

「$t$ 回のフェーズの後、左から $b$ 番目の位置にある小包はどれか」という形式のクエリに答えることで、機械が意図通りに動作するかどうかをテストするプログラムを作成してください。

入力

入力の 1 行目には、それぞれ小包の個数とクエリの個数を表す 2 つの整数 $n$ と $q$（$1 \le n, q \le 5 \cdot 10^5$）が与えられます。

2 行目には、小包の初期の並び順を表す $n$ 個の整数からなる列 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$、$a_i \ne a_j$）が与えられます。

続く $q$ 行にはクエリが与えられます。$i$ 行目には $i$ 番目のクエリを表す 2 つの整数 $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

機械は 3 回のフェーズを実行します：

$$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