二分探索木の回転（左） C編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

N 個の整数 t₁, t₂, ..., t_N と 1 個の整数 a が与えられます。

次のルールに従って二分探索木を作成した後、値が a であるノードを左回転し、木のノードを先行順で訪問した結果を出力してください。

なお、値が a であるノードは左回転できることが保証されています。

全てのノードについて、以下が成り立つ

・ 入力で与えられる t₁, t₂, ..., t_N の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい

木構造は、ノード同士が関係性を持つことで作ることができます。

この問題で各ノードが持つべき情報は以下の通りです。

・ ノードの値
・ 親ノードの情報
・ 左の子ノードの情報
・ 右の子ノードの情報

ノードの左回転は、以下のアルゴリズムで実装できます。

・ 対象ノードの右の子ノードを新しい親ノードにする
・ 対象ノードの右の子ノードの左の子ノードを、対象ノードの右の子にする
・ 新しい親ノードの左の子を対象ノードにする

入力される値

N
t₁ t₂ ... t_N
a

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

作成した木の N 個のノードの値 t_i を先行順で訪問した結果を出力してください。

訪問先にノードがある場合、訪問したノードの値 t_i を1行ずつ出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 3 ≦ N ≦ 100

・ 1 ≦ t_i ≦ 1000

・ a_i ∈ t

・ t_i ≠ t_j (i ≠ j)