プッシュ1 Perl編（paizaランク B 相当）

根を 0 として、各ノードに順番に番号が割り当てられた二分木を考えます。この二分木では、親ノードの番号を 2 倍して 1 または 2 を足したものが子ノードの番号となっています。

長さ 6 の数列が与えられます。この数列のインデックスと二分木の番号が対応しており、

数列の"親の番号"番目の要素は、"子の番号"番目の要素以下である

という条件(＊)が成り立っています。

整数 x が与えられます。はじめに与えられた長さ 6 の数列の末尾に x を追加したのち、条件(＊)が成り立つように要素を入れ替えた、長さ 7 の数列を出力してください。ただし、要素の入れ替えは、二分木で親と子の関係にあるインデックス同士でのみおこなうことができるものとします。

入力例 1 の場合を説明します。まず次のように数列と二分木が対応しています。今回の問題の場合、ノード 6 に対応する数値 x が 0 です。


ノード 6 の親はノード 2 であり、0 はノード 2 の数値 7 より小さいので入れ替えをおこないます。


同様に 0 はノード 0 の数値 1 より小さいので入れ替えをおこないます。


数値 x の 0 が根まで来たので、入れ替えは終了です。答えとなる、操作が終了したあとの二分木に対応する数列は以下のようになります。

0 3 1 5 12 9 7

このように、条件(＊)が成り立つようなデータ構造をヒープと呼びます。今回は二分木を用いているため二分ヒープと呼びます。そして今回の問題のように、ヒープに新しい要素を追加する操作を一般的にプッシュと呼びます。