Es gibt $n$ Pakete, nummeriert von $1$ bis $n$, die gerade in einem Lagerhaus angekommen sind. Sie kamen in der Reihenfolge $a_1, \dots, a_n$ an, und wir möchten sie so sortieren, dass sie sich in der Reihenfolge $1, 2, \dots, n$ befinden.
Die Sortiermaschine im Lagerhaus arbeitet in Phasen. Jede Phase nimmt eine Reihe $a_1, \dots, a_n$ von Paketen entgegen und geht wie folgt vor: Zuerst wird das erste Paket $a_1$ in eine neue Reihe gelegt. Dann wird für jedes Paket $a_i$ für $i = 2, \dots, n$ geprüft: Wenn $a_i$ größer als das letzte (am weitesten rechts stehende) Paket in der neuen Reihe ist, legt sie es an das Ende der Reihe. Andernfalls legt sie es an den Anfang der Reihe.
Wenn die neue Reihe noch nicht sortiert ist, dient sie als Eingabe für die nächste Phase der Sortiermaschine.
Schreibe ein Programm, das beim Testen hilft, ob die Maschine wie vorgesehen funktioniert, indem es Anfragen der Form „welches Paket befindet sich nach $t$ Phasen an der $b$-ten Stelle“ beantwortet.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ und $q$ ($1 \le n, q \le 5 \cdot 10^5$), die die Anzahl der Pakete bzw. die Anzahl der Anfragen angeben.
Die zweite Zeile enthält eine Folge von $n$ ganzen Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$), die die ursprüngliche Reihenfolge der Pakete darstellen.
Die nächsten $q$ Zeilen enthalten Anfragen; die $i$-te Zeile enthält zwei ganze Zahlen $t_i$ und $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), die die $i$-te Anfrage bezeichnen.
Ausgabe
Gib genau $q$ Zeilen aus. Die $i$-te Zeile soll die Antwort auf die $i$-te Anfrage enthalten.
Wenn die Maschine weniger als $t_i$ Phasen durchgeführt hat, gib $-1$ aus. Andernfalls gib aus, welches Paket sich nach $t_i$ durchgeführten Phasen an der Position $b_i$ von links befindet.
Beispiele
Eingabe 1
5 4 2 1 3 5 4 1 1 3 2 4 1 0 4
Ausgabe 1
4 2 -1 5
Hinweis 1
Die Maschine führt drei Phasen durch:
$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$
Eingabe 2
1 1 1 1 1
Ausgabe 2
-1