配点 : $300$ 点

問題文

あなたはアメーバの観察記録をつけました。

最初 $1$ 匹のアメーバがおり、番号は $1$ です。

観察記録は時系列順に $N$ 個あり、$i$ 番目の観察記録は「番号 $A_i$ のアメーバが分裂して消滅し、新たに $2$ 匹のアメーバが生まれ、それらにそれぞれ $2i,2i+1$ と番号をつけた」というものです。 このとき、アメーバ $A_i$ を アメーバ $2i,2i+1$ の親と呼びます。

各 $k=1,\ldots,2N+1$ について、アメーバ $k$ から何代親を遡るとアメーバ $1$ になるか求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• 観察記録は矛盾していない。すなわち- $1\leq A_i \leq 2i-1$
  • $A_i$ は相異なる整数
• $1\leq A_i \leq 2i-1$
• $A_i$ は相異なる整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

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

2
1 2

0
1
1
2
2

アメーバ $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$ になります。

4
1 3 5 2

0
1
1
2
2
3
3
2
2