問題
ムムムーン！サイキックアイドルのユッコですよ！
と言う彼女はサイキックの力でサイをキックするパフォーマンスで有名なサイキックアイドルのユッコである。
彼女は今日も相棒のサイの杏ちゃんと一緒にステージに出ることになっていたのだが、日頃の扱いがひどいことに対して怒ったサイの杏ちゃんが週休8日制を希望してしまった。
俗に言う働かない宣言である。
機嫌を取り戻してもらうためにユッコは杏ちゃんとボウリングに行くことにした。
知っての通り、ボウリングはピンを並べてそれをボールで倒すスポーツである。
ピンは三角形の形で並べられ、上から順に１番、２番、３番・・・と番号が付けられている。
基本的にはボウリングはこの要に４列に並べられている。
| 1 |
| 2 3 |
| 4 5 6 |
| 7 8 9 10|
これを高さ４の三角形と呼ぶことにする。
ユッコはサイキックが使えるアイドルである。彼女がムムムーンと念じればピンを改造することだって出来る。
具体的にはそれぞれのピンに対して右斜め下に倒れるか左斜め下に倒れるかを指定することが出来る。
１番ピンが左斜め下に倒れるように指定すれば１番ピンは２番ピンを倒す。
また、1番ピンが右斜め下に倒れるように指定すれば１番ピンは３番ピンを倒す。
全てのピンに対して倒れる方向を指定したユッコはいざ、ストライクを目指し、ボールを投げた。
しかし、ボールはガーターレーン一直線。このままではガーター間違いなしである。
するとそのとき、サイの杏ちゃんの鼻息で奇跡的に１番ピンのみが倒れた。
ここからピンがどのようにドミノ式で倒れたかを調べてほしい。
入力
N p1 p2 . . . p1+2+...+N
ボウリングのピンの三角形の高さNがまず与えられる。次に１番ピンから順にピンがどちらに倒れるかの情報が与えられる。
piが1の時、i番目のピンは左斜めに倒れる。
piが2の時、i番目のピンは右斜めに倒れる。
出力
ピンがどの順番で倒れたかを出力せよ。なお、最初に倒れるのは必ず１番ピンなので出力の最初は1である。ピンの番号を１つ出力するごとに改行をすること。
制約
全ての入出力ケースについて以下を満たす。
- 3≦N≦500
入出力例
入力例1
4 1 2 2 1 1 2 1 2 2 1
出力例1
1 2 5 8
解説
まず、このピンの三角形の高さは4なので、ピンの数は10である。(これについては三角数で調べましょう)
最初に１番ピンが倒れる。１番ピンは左斜め下に倒れるので、２番ピンを倒す。
２番ピンは右斜め下に倒れるので、５番ピンを倒す。
５番ピンは左斜め下に倒れるので、８番ピンを倒す。
８番ピンより後ろにピンは無いので、倒れるピンは順番に1,2,5,8となる。
これを出力する。
入力例2
5 1 1 2 2 1 2 1 2 1 2 2 1 1 2 1
出力例2
1 2 4 8 13
入力例3
3 1 1 2 1 2 2
出力例3
1 2 4
解説
彼女はサイキックアイドルである。再帰ックアイドルである。whileもしくはforでも出来る。