配点 : 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).
- 所有输入值都是整数。
小課題
- (12 点) N \leqq 9.
- (27 点) N \leqq 300.
- (21 点) N \leqq 5\,000.
- (29 点) N \leqq 200\,000.
- (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
此输入示例满足所有子任务约束。