Terdapat $n$ paket, yang dinomori dari $1$ hingga $n$, yang baru saja tiba di sebuah gudang. Paket-paket tersebut datang dalam urutan $a_1, \dots, a_n$, dan kita ingin mengurutkannya sehingga berada dalam urutan $1, 2, \dots, n$.

Mesin penyortir di gudang bekerja dalam beberapa fase. Setiap fase menerima sebaris paket $a_1, \dots, a_n$ dan bekerja sebagai berikut: Pertama, paket pertama $a_1$ diletakkan ke dalam baris baru. Kemudian, untuk setiap paket $a_i$ dengan $i = 2, \dots, n$, jika $a_i$ lebih besar daripada paket terakhir (paling kanan) di baris baru, mesin meletakkannya di ujung akhir baris. Jika tidak, mesin meletakkannya di bagian depan baris.

Jika baris baru tersebut belum terurut, baris itu menjadi masukan untuk fase berikutnya dari mesin penyortir.

Tulislah sebuah program yang membantu menguji apakah mesin bekerja sesuai rencana dengan menjawab kueri berbentuk "paket manakah yang berada di posisi ke-$b$ setelah $t$ fase".

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ dan $q$ ($1 \le n, q \le 5 \cdot 10^5$), yang masing-masing menyatakan jumlah paket dan jumlah kueri.

Baris kedua berisi barisan $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) yang menyatakan urutan awal paket.

$q$ baris berikutnya berisi kueri; baris ke-$i$ berisi dua bilangan bulat $t_i$ dan $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), yang menyatakan kueri ke-$i$.

Keluaran

Keluarkan tepat $q$ baris. Baris ke-$i$ harus berisi jawaban untuk kueri ke-$i$.

Jika mesin melakukan kurang dari $t_i$ fase, tuliskan $-1$. Jika tidak, tuliskan paket mana yang berada pada posisi ke-$b_i$ dari kiri setelah $t_i$ fase dilakukan.

Contoh

Masukan 1

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

Keluaran 1

4
2
-1
5

Catatan 1

Mesin akan melakukan tiga fase:

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

Masukan 2

1 1
1
1 1

Keluaran 2

-1