Найти второе наименьшее значение в BST

Допустим, у нас имеется пустое бинарное дерево поиска (BST) без каких-либо узлов. Необходимо выполнить два вида запросов:

  1. insert x — вставить значение x в BST

  2. smallest — вывести второе наименьшее значение в BST

Пусть количество запросов равно q. Требуется написать программу, которая будет обрабатывать эти запросы.

Входные данные

В первой строке входных данных содержится единственное число q (1 ≤ q ≤ 1000).

В следующих q строках приводятся запросы. Для всех операций insert значение x не превышает по модулю . Для всех запросов smallest гарантируется, что в BST содержится как минимум 2 элемента.

Выходные данные

Для каждого запроса smallest программа должна выводить второе наименьшее значение в бинарном дереве поиска.

Примеры

Входные данные

Выходные данные

7
insert 2
insert 1
smallest
insert 10
smallest
insert -1
smallest

2
2
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue