分数: 266 分
问题陈述
举行单败淘汰赛 N 玩家。在这里, N 是 2.
每个玩家都被分配了一个号码 1 to N,以及玩家的实力 i is S_i。所有玩家都有独特的优势,在任何比赛中,力量值较大的玩家总是获胜。输掉比赛的玩家将被淘汰,比赛继续进行,直到决出冠军为止。
自从 N 是 2,比赛包括 R = \log_2 N 回合。每轮比赛的对阵确定如下:
- 圆形 1: 玩家 2i-1 和玩家 2i 互相对战。这就是所谓的匹配 i 圆 1 (i = 1, 2, \ldots, N/2).
- 圆形 r (r \geq 2): 比赛获胜者 2j-1 和比赛获胜者 2j 上一轮(轮 r-1) 互相对抗。这就是所谓的匹配 j 圆 r (j = 1, 2, \ldots, N/2^r).
每轮比赛号码从 1 每轮都会重新分配。回合中 R,只有一场比赛,获胜者就是冠军。
对于每个玩家,确定该玩家被击败的轮数。然而,由于冠军从未被击败,输出 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
第一行给出玩家数量 N.
第二行给出了优点 每个玩家的 S_1, S_2, \ldots, S_N ,以空格分隔。
输出
输出 N 单行上用空格分隔的整数。的 i-th 值是玩家所在的回合数 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