BSTで2番目に小さい値を見つける

初期状態としてノードが1つも存在しない空のBinary Search Tree (BST) が与えられています。このBSTに対して、次の2種類のクエリを行います:

1. insert x - 値 x をBSTに挿入する

2. smallest - BSTの中で2番目に小さい要素を出力する

合計で q 個のクエリが与えられるので、これらのクエリを処理するプログラムを作成してください。

入力 (Input)

最初の行に、クエリの個数を示す整数 q (1 ≤ q ≤ 1000) が与えられます。

続く q 行には、各クエリが1行ずつ与えられます。すべての insert クエリにおいて、値 x は絶対値で10^9を超えません。また、すべての smallest クエリを行う時点で、BSTには少なくとも2つの要素が含まれていることが保証されています。

出力 (Output)

各 smallest クエリに対して、BST内で2番目に小さい要素を出力してください。

例 (Examples)