$0$ から $N-1$ までの整数を並び替えた長さ $N$ の順列 $P$ が与えられます。
以下の操作を最大 $30$ 回まで行って、 $P$ を昇順に並べ替えてください。
$1$ 回の操作では、次の 1 から 4 を順に行う。
0
と 1
からなる長さ $N$ の文字列 $S$ と、整数 $t$ ( $t = 0$ または $t = 1$ ) を宣言する。0
のとき、何もしない。1
のとき、0
のとき、何もしない。1
のとき、 $P_i$ を $C$ の先頭の要素に置き換え、 $C$ の先頭の要素を消す。例えば、$N = 7, P = {0, 4, 2, 3, 6, 5, 1}$ とします。
$S$ を "1101101" とし、$t = 1$ とした操作を $1$ 回行うと、以下の図のように $P = {3, 1, 2, 0, 4, 5, 6}$ となります。
入力は以下の形式で標準入力から与えられる。
$N$ $P_1$ $P_2$ $\ldots$ $P_N$
$30$ 回以内の操作で $P$ を昇順に並べ替えるような操作列の $1$ つを以下の形式で出力せよ。このような操作列は複数存在するかもしれないが、どれを出力しても正答となる。
$K$ $t_1$ $S_1$ $t_2$ $S_2$ $\vdots$ $t_K$ $S_K$
7 0 4 2 3 6 5 1
1 1 0100101
操作を行うと、$A = { 4, 6 }, B = { 1 }$ となり、 $t = 1$ より $C = { 1, 4, 6 }$ となります。
$P$ の要素を $C$ によって置き換えると、 $P = { 0, 1, 2, 3, 4, 5, 6 }$ となるので、この操作で $P$ を昇順に並べ替えることができます。
4 1 0 3 2
2 0 1100 0 0011
例えば以下のような出力も正答となります。
2 0 1111 1 0110
1 0
0
操作を行わなくても構いません。