AT_joig2026final_b 運動会 (Sports Festival)

JOIG 高中有 $N$ 个班级，编号为 $1$ 到 $N$。 今天是 JOIG 高中的运动会，目前只剩下最后一个项目。该项目开始前，第 $i$ 个班级（$1 \leq i \leq N$）的得分为 $A_i$。在最后的项目中，所有 $N$ 个班级都会参加，比赛结束后每个班级会被分配一个从 $1$ 到 $N$ 的不重复名次。 在最后的项目中，第 $j$ 名的班级可以获得 $N-j+1$ 分，然后确定最终的排名。最终排名以得分高者为先，如果分数相同则编号小的班级排名更靠前。 作为体育节执行委员会的葵同学，想提前为各个班级准备奖状。为此，她希望知道每个班级在所有可能的最终比赛名次分配方案下，各自最终可能获得多少种不同的排名。 请你编写程序，计算最后比赛结束后，每个班级可能获得的最终排名种类数。

输入通过标准输入按照以下格式给出： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出 $N$ 个整数，用空格隔开，一行输出。第 $i$ 个输出为第 $i$ 个班级可能获得的最终排名种类数。

### 小子任务 1. ($12$ 分) $N \leq 9$。 2. ($27$ 分) $N \leq 300$。 3. ($21$ 分) $N \leq 5\,000$。 4. ($29$ 分) $N \leq 200\,000$。 5. ($11$ 分) 没有额外约束。 --- ### 示例解释 1 例如，若最后的项目结果是各班按照编号顺序分别获得第 $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 第 1 班无论最后比赛如何排名，最终都排在第 1，因此输出第 1 个数为 $1$。 第 2 班与第 3 班，比赛结果会影响排名，排名高的获得第 2，排名低的获得第 3，因此输出分别为 $2$。 该输入示例符合所有小子任务的约束。 --- ### 示例解释 3 该输入示例符合所有小子任务的约束。 ### 数据范围 - $1 \leq N \leq 1\,000\,000$ - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$） - 输入的所有数均为整数。 由 ChatGPT 5 翻译