Trouver la kᵉ plus petite valeur dans un BST

Étant donné un arbre binaire de recherche (BST) initialement vide, vous devez exécuter deux types de requêtes :

1. insert x – insérer la valeur x dans le BST

2. smallest k – afficher le kᵉ plus petit élément du BST

Étant donné q requêtes, vous devez écrire un programme pour effectuer ces opérations.

Entrée

La première ligne de l’entrée contient un seul nombre q (1 ≤ q ≤ 1000).

Les q lignes suivantes contiennent les requêtes. Pour toutes les requêtes insert, la valeur de x ne dépasse pas en valeur absolue. Pour toutes les requêtes smallest, la valeur de k ne dépasse pas la taille actuelle de l’arbre.

Sortie

Pour chaque requête smallest, le programme doit afficher le kᵉ plus petit élément de l’arbre binaire de recherche.

Exemples