問題文

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

最初 $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$ は相異なる整数

入力

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

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

出力

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

入力例 1

2
1 2

出力例 1

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$ になります。

入力例 2

4
1 3 5 2

出力例 2

0
1
1
2
2
3
3
2
2