Finde den zweitkleinsten Wert in einem BST

Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten, sollen zwei Arten von Abfragen ausgeführt werden:

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

2. smallest – gibt das zweitkleinste Element im BST aus

Sie erhalten q Abfragen und sollen ein Programm schreiben, das diese Abfragen bearbeitet.

Eingabe

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

Die nächsten q Zeilen enthalten die Abfragen. Bei allen insert-Abfragen überschreitet der Wert von x nicht den Betrag von . Bei allen smallest-Abfragen ist garantiert, dass der BST mindestens 2 Elemente hat.

Ausgabe

Für jede smallest-Abfrage gibt das Programm das zweitkleinste Element im BST aus.

Beispiele