Maximum Tournament Survival Round

You are given a sequence of \(2^N\) positive integers. They compete in a single‐elimination tournament in the following way: In each round, the numbers (in the current order) are paired consecutively; in each match, the larger number wins and advances to the next round while the smaller one is eliminated. The tournament continues until only one number remains.

For each number in the initial sequence, determine the maximum round it can reach if the bracket is as favorable as possible. Note that every number participates in round 1. Hence, if a number loses in the first round, its maximum survival round is 1; if it wins in round 1 but loses in round 2, then its answer is 2; and so on. The champion will reach round \(N\) in a tournament of \(2^N\) numbers.

The key observation is that the tournament bracket is fixed once the initial order is given. For each index \(i\) (0-indexed), consider the aligned block in round \(r\) (with block size \(2^r\)). Let \(L = i - (i \bmod 2^r)\) be the starting index of that block. The number at \(i\) can survive round \(r\) if and only if it is the maximum element in the block \(a[L], a[L+1], \dots, a[L+2^r-1]\). Since every number participates in round 1 by default, the answer for each number is defined as:

[ \text{answer}[i] = \max{ r ;|; 1 \le r \le N \text{ and } a[i] = \max{a[L],a[L+1],\dots,a[L+2^r-1]}} ]

Output the maximum round (an integer between 1 and \(N\)) each number can survive, in the order of the initial sequence.

inputFormat

The first line contains a single integer \(N\) (where \(2^N\) is the number of competitors).

The second line contains \(2^N\) space-separated positive integers, representing the initial sequence.

outputFormat

Output \(2^N\) integers separated by spaces, where the \(i\)-th integer is the maximum round (from 1 to \(N\)) that the corresponding number can survive.

sample

2
1 3 2 4

1 2 1 2