A - Tournament Elimination Round Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

N 人の選手が参加するシングルエリミネーション方式のトーナメントが開催されます。ここで N は 2 のべき乗です。

各選手には 1 から N までの番号が付けられており、選手 i の強さは S_i です。すべての選手の強さは互いに異なり、対戦では必ず強さの値が大きい選手が勝ちます。負けた選手はトーナメントから脱落し、最終的に 1 人の優勝者が決まるまで試合が続けられます。

N は 2 のべき乗であるため、トーナメントは全体でちょうど R = \log_2 N ラウンド行われます。各ラウンドの対戦の組み合わせは次のように決まります。

  • ラウンド 1： 選手 2i-1 と選手 2i が対戦します。これをラウンド 1 の第 i 試合とします（i = 1, 2, \ldots, N/2）。
  • ラウンド r（r \geq 2）： 前のラウンド（ラウンド r-1）の第 2j-1 試合の勝者と第 2j 試合の勝者が対戦します。これをラウンド r の第 j 試合とします（j = 1, 2, \ldots, N/2^r）。

各ラウンドの試合番号は 1 から始まる番号でラウンドごとに付け直されます。ラウンド R では試合は 1 試合のみとなり、その勝者が優勝者です。

各選手について、その選手が敗北するラウンド番号を求めてください。ただし、優勝者は一度も敗北しないため、0 を出力してください。ラウンドは 1 から始まる番号で数えます。

制約

  • 2 \leq N \leq 2^{19}
  • N は 2 のべき乗である
  • 1 \leq S_i \leq N（1 \leq i \leq N）
  • S_i はすべて異なる
  • 入力はすべて整数である

入力

N
S_1 S_2 \ldots S_N

1 行目には選手の人数 N が与えられる。

2 行目には各選手の強さ S_1, S_2, \ldots, S_N がスペース区切りで与えられる。

出力

N 個の整数をスペース区切りで 1 行に出力せよ。i 番目の値は、選手 i が敗北するラウンド番号である。優勝者については 0 を出力せよ。

入力例 1

4
1 4 3 2

出力例 1

1 0 2 1

入力例 2

8
8 1 6 2 5 3 7 4

出力例 2

0 1 2 1 2 1 3 1

入力例 3

16
5 12 1 16 9 3 14 7 10 2 15 6 13 4 11 8

出力例 3

1 2 1 0 2 1 3 1 2 1 4 1 3 1 2 1

入力例 4

32
32 1 24 9 16 17 8 25 31 2 23 10 15 18 7 26 30 3 22 11 14 19 6 27 29 4 21 12 13 20 5 28

出力例 4

0 1 2 1 1 2 1 3 4 1 2 1 1 2 1 3 5 1 2 1 1 2 1 3 4 1 2 1 1 2 1 3

入力例 5

2
1 2

出力例 5

1 0

Score : 266 pts

Problem Statement

A single-elimination tournament is held with N players. Here, N is a power of 2.

Each player is assigned a number from 1 to N, and the strength of player i is S_i. All players have distinct strengths, and in any match, the player with the greater strength value always wins. A player who loses is eliminated from the tournament, and matches continue until a single champion is determined.

Since N is a power of 2, the tournament consists of exactly R = \log_2 N rounds. The matchups for each round are determined as follows:

  • Round 1: Player 2i-1 and player 2i play against each other. This is called match i of round 1 (i = 1, 2, \ldots, N/2).
  • Round r (r \geq 2): The winner of match 2j-1 and the winner of match 2j from the previous round (round r-1) play against each other. This is called match j of round r (j = 1, 2, \ldots, N/2^r).

Match numbers within each round are numbered starting from 1 and are reassigned for each round. In round R, there is only one match, and its winner is the champion.

For each player, determine the round number in which that player is defeated. However, since the champion is never defeated, output 0 for the champion. Rounds are numbered starting from 1.

Constraints

  • 2 \leq N \leq 2^{19}
  • N is a power of 2
  • 1 \leq S_i \leq N (1 \leq i \leq N)
  • All S_i are distinct
  • All input values are integers

Input

N
S_1 S_2 \ldots S_N

The first line gives the number of players N.

The second line gives the strengths S_1, S_2, \ldots, S_N of each player, separated by spaces.

Output

Output N integers separated by spaces on a single line. The i-th value is the round number in which player i is defeated. For the champion, output 0.

Sample Input 1

4
1 4 3 2

Sample Output 1

1 0 2 1

Sample Input 2

8
8 1 6 2 5 3 7 4

Sample Output 2

0 1 2 1 2 1 3 1

Sample Input 3

16
5 12 1 16 9 3 14 7 10 2 15 6 13 4 11 8

Sample Output 3

1 2 1 0 2 1 3 1 2 1 4 1 3 1 2 1

Sample Input 4

32
32 1 24 9 16 17 8 25 31 2 23 10 15 18 7 26 30 3 22 11 14 19 6 27 29 4 21 12 13 20 5 28

Sample Output 4

0 1 2 1 1 2 1 3 4 1 2 1 1 2 1 3 5 1 2 1 1 2 1 3 4 1 2 1 1 2 1 3

Sample Input 5

2
1 2

Sample Output 5

1 0