Encontrar o segundo menor valor em uma BST

Dada uma árvore binária de busca (BST) vazia, sem nenhum nó, você precisa realizar 2 tipos de consultas:

1. insert x - insere o valor x na BST

2. smallest - exibe o segundo menor elemento na BST

Dadas q consultas, o objetivo é escrever um programa que processe essas consultas.

Entrada

A primeira linha da entrada contém um único número q (1 ≤ q ≤ 1000).

As próximas q linhas contêm as consultas. Para cada consulta do tipo insert, o valor de x não excede em valor absoluto. Em cada consulta smallest, é garantido que a BST possui pelo menos 2 elementos.

Saída

Para cada consulta smallest, o programa deve imprimir o segundo menor elemento na árvore binária de busca (BST).

Exemplos