Problem Description

$2^N$ people, person $1$, person $2$, ..., person $2^N$, lined up in a row to participate in a tournament. The tournament was conducted as follows:

• Round 1: For each $i$ satisfying $1 \leq i \leq 2^{N-1}$, person $2i-1$ and person $2i$ fight. One of them wins, and the winner remains.
• Round $i$ ($i \geq 2$): The people who remained from the previous round ($i-1$) are lined up in order from left to right, and pairs are formed from left to right. Each pair of two people fight. One of them wins, and the winner remains.

The records of each match have been lost, but it was recorded that the strength of person $i$ was $A_i$. When two people fight, the one with the higher strength value wins.

For each person, determine in which round they fought for the last time.

Input Format

The input is given from the standard input in the following format:

$N$ $A_1$ $A_2$ $\cdots$ $A_{2^N}$

Output Format

Output $2^N$ lines. The $i$-th line should contain the round in which person $i$ fought for the last time.

Sample Input and Output

Sample Input #1

2
2 4 3 1

Sample Output #1

1
2
2
1

Sample Input #2

1
2 1

Sample Output #2

1
1

Sample Input #3

3
4 7 5 1 6 3 2 8

Sample Output #3

1
3
2
1
2
1
1
3

Notes/Hints

Note

Discussion of this problem is prohibited until May 2, 2020, 18:00 JST. If discussed, compensation may be claimed.

It is okay to announce the total score and certification level after the test, but please do not disseminate information about which problems were solved.

Constraints

• $1 \leq N \leq 16$
• $1 \leq A_i \leq 2^N$
• The elements of $A$ are distinct

Sample Explanation 1

• Round 1: Person $1$ (strength $2$) and person $2$ (strength $4$) fight, and person $2$ remains. Also, person $3$ (strength $3$) and person $4$ (strength $1$) fight, and person $3$ remains.
• Round 2: Person $2$ and person $3$ fight, and person $2$ wins.

Therefore, person $1$ and person $4$ fought for the last time in round $1$, and person $2$ and person $3$ fought for the last time in round $2$.

Sample Explanation 2

When there are only $2$ participants, both have their last fight in round $1$.

见题面 Input 部分

见题面 Output 部分