← 返回题目列表

AtCoder · joig2026final_b

B. 体育节

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

配点 : 100 点

問題文

JOIG 高中有 编号至1 从 N 有 N 课程。

今天是JOIG高中运动会,只剩下最后一场比赛了。最后一场比赛开始前的课程 i (1\leqq i \leqq N) 的分数是 A_i 。 在最后的比赛中, 所有N 班级都参加了,并且每个班级 来自 1 分配最高 N 的不同排名。

决赛中, j (1\leqq j \leqq N) 为班级成绩 N - j + 1 积分相加,确定最终排名。 最终排名时,分数最高的班级排名靠前,平局的情况下,分数较低的班级排名靠前。

JOIG 苍井先生是高中运动会执行委员会的成员,他想提前准备好证书,以便在比赛结束后颁发给各个班级。 所以我想知道每个班级最终能拿多少个不同的名次。

编写一个程序,计算最后一场比赛结束后每个班级可能的最终排名数。


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

到标准输出 N 由空格分隔的整数,1 行。 i (1\leqq i \leqq N) 要输出的第一个整数是类别 令 为 i 可以取得的最终排名数。


制約

  • 1 \leqq N \leqq 1\,000\,000.
  • 1 \leqq A_i \leqq 10^9 (1\leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (12 点) N \leqq 9.
  2. (27 点) N \leqq 300.
  3. (21 点) N \leqq 5\,000.
  4. (29 点) N \leqq 200\,000.
  5. (11 点)没有额外的限制。

入力例 1

4
5 2 3 6

出力例 1

3 2 3 3

举例来说,上次比赛的结果按班级编号排序。 考虑 2 位,3 位,1 位,4 的情况。每个班级的分数 添加了 3 点,2 点,4 点,1 点,因此 最后的分数是按顺序排列的 8 点,4 点,7 点,7 成为重点。因此,最终排名为 1 位,4 位,2 位,3 。

这样,在考虑最终比赛中所有可能的排名时,每个班级最终可能的排名如下。

  • 类 1 最终能取得的排名是 1 位,2 位,3 秩 3 类型。
  • 类 2 最终能取得的排名是 3 位,4 秩 2 类型。
  • 类 3 最终能取得的排名是 2 位,3 位,4 秩 3 类型。
  • 类 4 最终能取得的排名是 1 位,2 位,3 秩 3 类型。

此输入示例满足所有子任务约束。


入力例 2

3
1000000000 1 1

出力例 2

1 2 2

类 1 无论最终比赛结果如何,均以最终排名为准。 1 ,所以1 第 1 。 求

类 2 和班级 3 如果你在上一场比赛中获得更高的排名就更好了。 2 最好采取较低的排名。 3 ,所以2 th 和 每 3 第 2 。 求

此输入示例满足所有子任务约束。


入力例 3

7
11 10 17 10 15 7 11

出力例 3

7 6 3 6 5 4 6

此输入示例满足所有子任务约束。