AT_abc274_c [ABC274C] Ameba

[problemUrl]: https://atcoder.jp/contests/abc274/tasks/abc274_c あなたはアメーバの観察記録をつけました。 最初 $ 1 $ 匹のアメーバがおり、番号は $ 1 $ です。 観察記録は時系列順に $ N $ 個あり、$ i $ 番目の観察記録は「番号 $ A_i $ のアメーバが分裂して消滅し、新たに $ 2 $ 匹のアメーバが生まれ、それらにそれぞれ $ 2i,2i+1 $ と番号をつけた」というものです。 このとき、アメーバ $ A_i $ を アメーバ $ 2i,2i+1 $ の親と呼びます。 各 $ k=1,\ldots,2N+1 $ について、アメーバ $ k $ から何代親を遡るとアメーバ $ 1 $ になるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ 2N+1 $ 行出力せよ。$ k $ 行目にはアメーバ $ k $ から何代親を遡るとアメーバ $ 1 $ になるかを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ - 観察記録は矛盾していない。すなわち - $ 1\leq\ A_i\ \leq\ 2i-1 $ - $ A_i $ は相異なる整数 ### Sample Explanation 1 アメーバ $ 1 $ からアメーバ $ 2,3 $ が生まれ、アメーバ $ 2 $ からアメーバ $ 4,5 $ が生まれました。 - アメーバ $ 1 $ は $ 0 $ 代遡るとアメーバ $ 1 $ になります。 - アメーバ $ 2 $ は $ 1 $ 代遡るとアメーバ $ 1 $ になります。 - アメーバ $ 3 $ は $ 1 $ 代遡るとアメーバ $ 1 $ になります。 - アメーバ $ 4 $ は $ 1 $ 代遡るとアメーバ $ 2 $ になり、$ 2 $ 代遡るとアメーバ $ 1 $ になります。 - アメーバ $ 5 $ は $ 1 $ 代遡るとアメーバ $ 2 $ になり、$ 2 $ 代遡るとアメーバ $ 1 $ になります。