Finde den k-kleinsten Wert in einem BST

Angenommen, Sie beginnen mit einem leeren Binary Search Tree (BST) ohne Knoten. Sie sollen zwei Arten von Anfragen bearbeiten:

1. insert x – fügt den Wert x in den BST ein

2. smallest k – gibt das k-kleinste Element im BST aus

Gegeben sind q Anfragen. Sie sollen ein Programm schreiben, um diese Anfragen auszuführen.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne Zahl q (1 ≤ q ≤ 1000).

Die nächsten q Zeilen enthalten die Anfragen. Für alle insert-Anfragen übersteigt der Wert von x nicht den Betrag von . Für alle smallest-Anfragen bleibt der Wert von k innerhalb der aktuellen Größe des Baums.

Ausgabe

Für jede smallest-Anfrage soll das k-kleinste Element im Binary Search Tree ausgegeben werden.

Beispiele