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