I - トーナメント 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

人 1、人 2、…、人 2^N の 2^N 人が一列に並んでトーナメントを行いました。このトーナメントは以下のようにして行われました。

  • 1 回戦: 1 \leq i \leq 2^{N-1} を満たすそれぞれの i について、人 2i-1 と人 2i が戦う。どちらか一方が勝つので、勝った方が残る。
  • i 回戦 (i \geq 2): i - 1 回戦で残った人が番号順に左から並び、左から 2 人ずつペアになり、各ペア内の 2 人が戦う。どちらか一方が勝つので、勝った方が残る。

各試合の記録は失われてしまいましたが、人 i の強さが A_i であったことは記録に残っていました。ここで、2 人の人が戦ったとき、強さの値が大きい方が勝ちます。

それぞれの人について、その人が最後に戦ったのは何回戦か求めてください。

制約

  • 1 \leq N \leq 16
  • 1 \leq A_i \leq 2^N
  • A の要素は相異なる

入力

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

N
A_1 A_2 \cdots A_{2^N}

出力

2^N 行出力せよ。i 行目には、人 i が最後に戦ったのは何回戦かを出力せよ。

入力例 1

2
2 4 3 1

出力例 1

1
2
2
1
  • 1 回戦: 人 1 (強さ 2) と人 2 (強さ 4) が戦い、人 2 が勝ち残った。また、人 3 (強さ 3) と人 4 (強さ 1) が戦い、人 3 が勝ち残った。
  • 2 回戦: 人 2 と人 3 が戦い、人 2 が勝った。

したがって、人 1 と 人 4 が最後に戦ったのは 1 回戦、人 2 と人 3 が最後に戦ったのは 2 回戦です。

入力例 2

1
2 1

出力例 2

1
1

参加者が 2 人しかいない場合は、どちらも 1 回戦が最後の戦いになります。

入力例 3

3
4 7 5 1 6 3 2 8

出力例 3

1
3
2
1
2
1
1
3

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

2^N players with integer IDs - Player 1, Player 2, ..., Player 2^N - stood in a line and played an elimination tournament, as follows:

  • Round 1: For each i such that 1 \leq i \leq 2^{N-1}, Player 2i-1 and Player 2i fight until one of them wins and survives.
  • Round i (i \geq 2): The players survived Round i-1 stand in a line in ascending order of ID. Then, for each i such that 1 \leq i \leq 2^{N-i}, the (2i-1)-th and the $(2i)-th players from the left fight until one of them wins and survives.

While the record of each fight is now lost, our record says that the strength of Player i was A_i. Here, when two players fight, the player with the greater strength wins.

For each of the players, find the last round in which that player fought.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_{2^N}

Output

Print 2^N. The i-th line should contain the integer representing the last round in which Player i fought.

Sample Input 1

2
2 4 3 1

Sample Output 1

1
2
2
1
  • Round 1: Player 2 (strength: 4) fought against Player 1 (strength: 2) and won. Also, Player 3 (strength: 3) fought against Player 4 (strength: 1) and won.
  • Round 2: Player 2 fought against Player 3 and won.

Thus, the last rounds in which Player 1,2,3,4 fought are Round 1,2,2,1, respectively.

Sample Input 2

1
2 1

Sample Output 2

1
1

There were just two players, in which case Round 1 was the last round for both of them.

Sample Input 3

3
4 7 5 1 6 3 2 8

Sample Output 3

1
3
2
1
2
1
1
3