Det finns $n$ paket, numrerade från $1$ till $n$, som precis har anlänt till ett lager. De kom i ordningen $a_1, \dots, a_n$, och vi vill sortera dem så att de hamnar i ordningen $1, 2, \dots, n$.

Sorteringsmaskinen i lagret arbetar i faser. Varje fas tar emot en rad $a_1, \dots, a_n$ av paket och gör på följande sätt: Först läggs det första paketet $a_1$ i en ny rad. Sedan, för varje paket $a_i$ för $i = 2, \dots, n$, om $a_i$ är större än det sista (längst till höger) paketet i den nya raden, lägger maskinen det i slutet av raden. Annars lägger den det längst fram i raden.

Om den nya raden inte är sorterad fungerar den som indata till nästa fas av sorteringsmaskinen.

Skriv ett program som hjälper till att testa om maskinen fungerar som tänkt genom att svara på frågor av formen "vilket paket ligger på den $b$-te platsen efter $t$ faser".

Indata

Den första raden i indatan innehåller två heltal $n$ och $q$ ($1 \le n, q \le 5 \cdot 10^5$), som anger antalet paket respektive antalet frågor.

Den andra raden innehåller en följd av $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) som representerar paketens ursprungliga ordning.

De följande $q$ raderna innehåller frågor; den $i$-te raden innehåller två heltal $t_i$ och $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), som anger den $i$-te frågan.

Utdata

Skriv ut exakt $q$ rader. Den $i$-te raden ska innehålla svaret på den $i$-te frågan.

Om maskinen utförde färre än $t_i$ faser, skriv $-1$. Annars, skriv vilket paket som befinner sig på position $b_i$ från vänster efter att $t_i$ faser har utförts.

Exempel

Indata 1

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

Utdata 1

4
2
-1
5

Förklaring 1

Maskinen kommer att utföra tre faser:

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

Indata 2

1 1
1
1 1

Utdata 2

-1