Overview

This problem involves directly simulating the progression of a tournament and recording “which round each player lost in” for the player who loses each match.
Since only one person remains as the champion, that player’s answer is \(0\).

Analysis

The key point of this problem is that the matchup pairings are completely fixed.

• Round 1: \((1,2), (3,4), \dots\)
• Round 2: the winners of Round 1 are paired in order from left to right
• Subsequent rounds follow the same pattern

In other words, by repeatedly “matching adjacent players in the current ordering,” we faithfully reproduce the tournament progression described in the problem statement.

Also, since the strengths \(S_i\) are all distinct, there are no draws, and the winner of each match is uniquely determined.
Therefore, for each match, we simply:

• Set ans[player_index] = current_round for the loser
• Add the winner to the next round’s array

and that’s all we need.

About the Naive Approach

If you try an approach like “individually determine where each player loses,” you end up redundantly recomputing the same matches, which is inefficient.
Since simulating the entire tournament once yields the answers for all players simultaneously, processing everything together is optimal.

Algorithm

1. Store the players remaining in the current round in current, in tournament order. Each element is (strength, index).
2. Start with round_no = 1.
3. Repeat until the length of current becomes 1:
   • Take players two at a time and have them compete.
   • Add the stronger one to nxt (advancing to the next round).
   • Record round_no in ans[index] for the weaker one.
4. When the loop ends, the one person remaining in current is the champion, so set their ans[index] = 0.
5. Output ans.

For example, if \(N=8\):
Round 1 reduces 8 players to 4, Round 2 reduces 4 to 2, Round 3 reduces 2 to 1 — the number of players halves each time.
We simply fill in the round number at which each player lost during this process.

Complexity

• Time complexity: \(O(N)\)
  (The total number of matches across all rounds is \(N/2 + N/4 + \cdots + 1 = N-1\))
• Space complexity: \(O(N)\)
  (For ans and the survivor array for each round)

Implementation Notes

• Player numbers are \(1\)-indexed in the input, but using \(0\)-indexed arrays in your implementation makes array access simpler.

• It is important that current stores not only the strength but also the original player number (index).
  Without this, you cannot determine “whose answer to update.”

• Since the champion never loses during the loop, you explicitly set their answer to \(0\) at the end (even if the initial value is 0, explicitly setting it is safer to make the intent clear).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = list(map(int, input().split()))

    # current players in bracket order: (strength, index)
    current = [(S[i], i) for i in range(N)]
    ans = [0] * N
    round_no = 1

    while len(current) > 1:
        nxt = []
        for i in range(0, len(current), 2):
            a = current[i]
            b = current[i + 1]
            if a[0] > b[0]:
                ans[b[1]] = round_no
                nxt.append(a)
            else:
                ans[a[1]] = round_no
                nxt.append(b)
        current = nxt
        round_no += 1

    # champion
    ans[current[0][1]] = 0

    print(*ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.