C - Ameba Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 は相異なる整数

入力

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

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

Score : 300 points

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

  • 1 \leq N \leq 2\times 10^5
  • The records are consistent. That is:
    • 1\leq A_i \leq 2i-1.
    • A_i are distinct integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print 2N+1 lines. The k-th line should contain the generation distance between amoeba 1 and amoeba k.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

  • Amoeba 1 is zero generations away from amoeba 1.
  • Amoeba 2 is one generation away from amoeba 1.
  • Amoeba 3 is one generation away from amoeba 1.
  • Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
  • Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2