← 返回题目列表

AtCoder · awc0078_c

C. 被淘汰的选手和积分榜

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥正在组织一场马拉松比赛 N 参与者。球员编号从 1 to N,以及每个玩家 i (i = 1, 2, \ldots, N) 具有“耐力值” L_i。耐力值是以下排列 1 通过 N,这意味着它们是不同的整数 1 和 N 包括在内。

在比赛中, N 玩家在开始时从左到右排成一排。最初,玩家 i 位于 i从左边算起第一个位置。换句话说,每个玩家的号码与他们的初始位置相匹配。

比赛开始后,选手按照体力值从小到大的顺序一一退场。即具有体力值的玩家 1 先退役,然后是有体力值的球员 2,以此类推,直到最后有体力值的玩家 N 退休。

当一名球员退役时,他们会离开该排。剩下的玩家保持相对顺序并缩小间隙,再次从左侧形成连续的一排。

作为记录保持者,高桥想要记录, 就在之前 每位球员退场,该球员在剩余球员中占据左侧第什么位置。这里,“就在退役之前”意味着球员本人此时仍在队伍中。

对于 k = 1, 2, \ldots, N 按顺序,从左边开始确定有体力值的玩家的位置 k 就在该玩家退役之前的剩余玩家(包括他们自己)中。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_i \leq N
  • L_1, L_2, \ldots, L_N 是一个排列 1 通过 N
  • 所有输入值均为整数

输入

N
L_1 L_2 \ldots L_N
  • 第一行包含一个整数 N,玩家数量。
  • 第二行包含 N 整数 L_i 以空格分隔,代表玩家的体力值 i (i = 1, 2, \ldots, N).

输出

打印 N 行。的 k- 第行 (k = 1, 2, \ldots, N) 应包含一个整数,表示具有耐力值的玩家左侧的位置 k 就在该玩家退役之前的剩余玩家(包括他们自己)中。


样本输入 1

5
3 1 4 5 2

示例输出 1

2
4
1
1
1

示例输入 2

4
4 3 2 1

示例输出 2

4
3
2
1

示例输入 3

10
5 3 8 1 10 2 7 9 4 6

示例输出 3

4
5
2
6
1
5
3
1
2
1

示例输入 4

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

示例输出 4

8
13
4
14
2
10
7
12
4
9
6
1
8
2
6
3
4
1
2
1

示例输入 5

1
1

示例输出 5

1