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