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?

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.

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.

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

见题面 Input 部分

见题面 Output 部分